当前位置：首页 > ds >正文

【LeetCode 热题 100】300. 最长递增子序列——（解法一）记忆化搜索

ds 2025/8/24 8:10:25

Problem: 300. 最长递增子序列

文章目录

整体思路
完整代码
时空复杂度
- 时间复杂度：O(N^2)
- 空间复杂度：O(N)

整体思路

这段代码旨在解决经典的 “最长递增子序列” (Longest Increasing Subsequence, LIS) 问题。问题要求在一个未排序的整数数组中，找到一个子序列，该子序列中的元素严格递增，并且该子序列的长度是所有可能情况中最长的。返回这个最长长度。

该算法采用的是一种 自顶向下（Top-Down）的动态规划 方法，即 记忆化搜索 (Memoization)。它通过递归地寻找以每个元素为结尾的最长递增子序列的长度，最终找出全局的最长长度。

算法的核心逻辑步骤如下：

状态定义与递归关系：
- 算法的核心是递归函数 dfs(i)，其状态定义为：
  dfs(i) = 在 nums 数组中，以 nums[i] 为结尾的最长递增子序列的长度。
- 为了计算 dfs(i)，我们需要考虑 nums[i] 可以接在哪个递增子序列的后面。nums[i] 只能接在某个以 nums[j]（其中 j < i）为结尾的递增子序列之后，并且必须满足 nums[j] < nums[i]。
- 因此，dfs(i) 的值等于 1 (代表 nums[i] 本身) 加上 “所有满足 j < i 且 nums[j] < nums[i] 的 dfs(j) 中的最大值”。
- 这形成了递归关系：dfs(i) = 1 + max(dfs(j))，其中 0 <= j < i 且 nums[j] < nums[i]。如果没有这样的 j，则 max(dfs(j)) 为 0，此时 dfs(i) = 1（子序列只包含 nums[i] 自己）。
记忆化 (Memoization)：
- 纯粹的递归会导致子问题（如 dfs(j)）被多次重复计算。
- 为了优化，算法使用了一个 memo 数组。memo[i] 用于存储 dfs(i) 的计算结果。
- 在 dfs(i) 函数的开头，会先检查 memo[i] 是否已经被计算过（在此代码中，通过 > 0 判断）。如果已经计算过，就直接返回存储的结果。
主函数逻辑：
- lengthOfLIS 函数是主入口。它需要找到全局的最长递增子序列。
- 全局的最长递增子序列必然会以数组中的某个元素 nums[i] 为结尾。
- 因此，主函数通过一个 for 循环，遍历所有可能的结尾位置 i（从 0 到 n-1），分别调用 dfs(i) 来计算以 nums[i] 为结尾的LIS长度。
- 在循环中，用一个 ans 变量来记录并更新所有 dfs(i) 结果中的最大值。
返回结果：
- 循环结束后，ans 中存储的就是全局的最长递增子序列的长度。

完整代码

class Solution {/*** 计算数组中最长递增子序列的长度。* @param nums 输入的整数数组* @return 最长递增子序列的长度*/public int lengthOfLIS(int[] nums) {int n = nums.length;// ans: 用于存储全局的最长递增子序列长度。int ans = 0;// memo: 记忆化数组。memo[i] 存储 dfs(i) 的结果，即以 nums[i] 结尾的 LIS 长度。// 初始化为 0，因为 LIS 长度至少为 1，0 可以作为“未计算”的标志。int[] memo = new int[n];// 遍历所有可能的结尾位置 ifor (int i = 0; i < n; i++) {// 计算以 nums[i] 结尾的 LIS 长度，并用它来更新全局最大值 ans。ans = Math.max(ans, dfs(i, nums, memo));}return ans;}/*** 记忆化搜索函数，计算以 nums[i] 结尾的最长递增子序列的长度。* @param i 当前子序列的结尾元素的索引* @param nums 原始数组* @param memo 记忆化数组* @return 以 nums[i] 结尾的 LIS 长度*/private int dfs(int i, int[] nums, int[] memo) {// 记忆化检查：如果 memo[i] > 0，说明这个子问题已经计算过，直接返回。if (memo[i] > 0) {return memo[i];}// res: 用于记录在 nums[i] 之前的所有 LIS 长度中的最大值。int res = 0;// 遍历 i 之前的所有元素 jfor (int j = 0; j < i; j++) {// 如果找到一个 nums[j] 小于 nums[i]，说明 nums[i] 可以接在以 nums[j] 结尾的 LIS 后面。if (nums[j] < nums[i]) {// 我们取所有可能的“前导”LIS长度中的最大值。res = Math.max(res, dfs(j, nums, memo));}}// 最终结果是：前面最长的 LIS 长度 res，加上 nums[i] 本身 (长度+1)。// 在返回前，将结果存入 memo 数组。return memo[i] = res + 1;}
}

时空复杂度

时间复杂度：O(N^2)

状态数量：由于记忆化的存在，每个子问题 dfs(i)（i 从 0 到 n-1）只会被实际计算一次。总共有 O(N) 个不同的状态。
每个状态的计算时间：在 dfs(i) 函数内部，主要的开销来自 for 循环，它从 j=0 遍历到 i-1。在最坏的情况下（当 i 接近 n-1 时），这个循环执行大约 O(N) 次。
主函数循环：外层的 for 循环也执行 N 次。但由于记忆化，dfs(i) 的实际计算只发生一次。
综合分析：
总时间复杂度 = (状态数量) × (每个状态的计算时间) = O(N) * O(N) = O(N^2)。
或者可以这样看：总共有 N 个 memo 条目需要填充，填充每个 memo[i] 需要一个 O(i) 的循环。总计算量是 Σ(i=0 to n-1) O(i) = O(N^2)。