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

动态规划求解leetcode300.最长递增子序列（LIS）详解

web 2025/5/6 23:55:34

给你一个整数数组 nums ，找到其中最长严格递增子序列的长度。

子序列 是由数组派生而来的序列，删除（或不删除）数组中的元素而不改变其余元素的顺序。例如，[3,6,2,7] 是数组 [0,3,1,6,2,2,7] 的子序列。

示例 1：

输入：nums = [10,9,2,5,3,7,101,18]
输出：4
解释：最长递增子序列是 [2,3,7,101]，因此长度为 4 。

示例 2：

输入：nums = [0,1,0,3,2,3]
输出：4

示例 3：

输入：nums = [7,7,7,7,7,7,7]
输出：1

关键点

双重循环结构：外层循环遍历每个元素作为子序列结尾，内层循环检查所有可能的前驱元素
递增条件：只有当 nums[j] < nums[i] 时才考虑状态转移
时间复杂度：O(n²)，因为有两层嵌套循环

核心思路

定义状态：
- dp[i] 表示以 nums[i] 结尾的最长递增子序列的长度
- 初始时每个元素本身就是一个长度为1的子序列，所以初始化 dp 数组全为1
状态转移：
- 对于每个 i（当前元素），检查所有 j < i（前面的元素）
- 如果 nums[j] < nums[i]（满足递增条件），则尝试更新 dp[i]：
```
dp[i] = Math.max(dp[i], dp[j] + 1)
```
  这表示如果接在 nums[j] 后面能形成更长的子序列，就更新 dp[i]
记录结果：
- 在计算过程中持续维护一个全局最大值 res
- 最终 res 就是整个数组的最长递增子序列长度

// Dynamic programming.
class Solution {public int lengthOfLIS(int[] nums) {if(nums.length == 0) return 0;int[] dp = new int[nums.length];int res = 0;Arrays.fill(dp, 1);for(int i = 0; i < nums.length; i++) {for(int j = 0; j < i; j++) {if(nums[j] < nums[i]) dp[i] = Math.max(dp[i], dp[j] + 1);}res = Math.max(res, dp[i]);}return res;}
}

示例数组

nums = [10, 9, 2, 5, 3, 7, 101, 18]

算法步骤解析

初始化：
- 创建dp数组，长度与nums相同，初始值全为1（因为每个元素本身就是一个长度为1的子序列）
```
dp = [1, 1, 1, 1, 1, 1, 1, 1]
```
双重循环处理：
- 外层循环：i从0到n-1
- 内层循环：j从0到i-1
逐步计算过程：

i=0 (nums[0]=10):
- j无（因为i=0时j从0到-1）
- dp保持不变：[1, 1, 1, 1, 1, 1, 1, 1]
- res=1
i=1 (nums[1]=9):
- j=0: nums[0]=10 > nums[1]=9 → 不更新
- dp保持不变：[1, 1, 1, 1, 1, 1, 1, 1]
- res=1
i=2 (nums[2]=2):
- j=0: nums[0]=10 > nums[2]=2 → 不更新
- j=1: nums[1]=9 > nums[2]=2 → 不更新
- dp保持不变：[1, 1, 1, 1, 1, 1, 1, 1]
- res=1
i=3 (nums[3]=5):
- j=0: nums[0]=10 > nums[3]=5 → 不更新
- j=1: nums[1]=9 > nums[3]=5 → 不更新
- j=2: nums[2]=2 < nums[3]=5 → dp[3] = max(dp[3], dp[2]+1) = max(1, 2) = 2
- dp更新为：[1, 1, 1, 2, 1, 1, 1, 1]
- res=2
i=4 (nums[4]=3):
- j=0: nums[0]=10 > nums[4]=3 → 不更新
- j=1: nums[1]=9 > nums[4]=3 → 不更新
- j=2: nums[2]=2 < nums[4]=3 → dp[4] = max(dp[4], dp[2]+1) = max(1, 2) = 2
- j=3: nums[3]=5 > nums[4]=3 → 不更新
- dp更新为：[1, 1, 1, 2, 2, 1, 1, 1]
- res=2
i=5 (nums[5]=7):
- j=0: nums[0]=10 > nums[5]=7 → 不更新
- j=1: nums[1]=9 > nums[5]=7 → 不更新
- j=2: nums[2]=2 < nums[5]=7 → dp[5] = max(dp[5], dp[2]+1) = max(1, 2) = 2
- j=3: nums[3]=5 < nums[5]=7 → dp[5] = max(dp[5], dp[3]+1) = max(2, 3) = 3
- j=4: nums[4]=3 < nums[5]=7 → dp[5] = max(dp[5], dp[4]+1) = max(3, 3) = 3
- dp更新为：[1, 1, 1, 2, 2, 3, 1, 1]
- res=3
i=6 (nums[6]=101):
- j=0: nums[0]=10 < nums[6]=101 → dp[6] = max(dp[6], dp[0]+1) = max(1, 2) = 2
- j=1: nums[1]=9 < nums[6]=101 → dp[6] = max(dp[6], dp[1]+1) = max(2, 2) = 2
- j=2: nums[2]=2 < nums[6]=101 → dp[6] = max(dp[6], dp[2]+1) = max(2, 2) = 2
- j=3: nums[3]=5 < nums[6]=101 → dp[6] = max(dp[6], dp[3]+1) = max(2, 3) = 3
- j=4: nums[4]=3 < nums[6]=101 → dp[6] = max(dp[6], dp[4]+1) = max(3, 3) = 3
- j=5: nums[5]=7 < nums[6]=101 → dp[6] = max(dp[6], dp[5]+1) = max(3, 4) = 4
- dp更新为：[1, 1, 1, 2, 2, 3, 4, 1]
- res=4
i=7 (nums[7]=18):
- j=0: nums[0]=10 < nums[7]=18 → dp[7] = max(dp[7], dp[0]+1) = max(1, 2) = 2
- j=1: nums[1]=9 < nums[7]=18 → dp[7] = max(dp[7], dp[1]+1) = max(2, 2) = 2
- j=2: nums[2]=2 < nums[7]=18 → dp[7] = max(dp[7], dp[2]+1) = max(2, 2) = 2
- j=3: nums[3]=5 < nums[7]=18 → dp[7] = max(dp[7], dp[3]+1) = max(2, 3) = 3
- j=4: nums[4]=3 < nums[7]=18 → dp[7] = max(dp[7], dp[4]+1) = max(3, 3) = 3
- j=5: nums[5]=7 < nums[7]=18 → dp[7] = max(dp[7], dp[5]+1) = max(3, 4) = 4
- j=6: nums[6]=101 > nums[7]=18 → 不更新
- dp更新为：[1, 1, 1, 2, 2, 3, 4, 4]
- res=4