最长递增子序列（LIS）问题的动态规划解法 最长递增子序列（Longest Increasing Subsequence，LIS）问题要求找出给定序列中最长的严格递增子序列的长度。例如，对于序列 [ 10, 9, 2, 5, 3, 7, 101, 18]，最长递增子序列之一是 [ 2, 3, 7, 101 ]，长度为 4。下面逐步讲解动态规划解法。 1. 问题分析 输入 ：一个整数数组 nums。 输出 ：最长递增子序列的长度。 关键点 ：子序列不要求连续，但必须严格递增（即每个元素严格大于前一个元素）。 2. 动态规划状态定义 定义 dp[i] 表示以第 i 个元素结尾的最长递增子序列的长度。 例如， dp[3] 表示以 nums[3] 结尾的 LIS 长度。 3. 状态转移方程 对于每个位置 i ，需要检查所有 j < i 的元素： 如果 nums[j] < nums[i] ，说明 nums[i] 可以接在以 nums[j] 结尾的 LIS 后面，形成更长的序列，此时 dp[i] = max(dp[i], dp[j] + 1) 。 如果不存在这样的 j ，则 dp[i] = 1 （仅包含自身）。 转移方程： dp[i] = max(dp[i], dp[j] + 1) ，对所有 j < i 且 nums[j] < nums[i] 成立。 4. 算法步骤 初始化 dp 数组，长度与 nums 相同，所有值设为 1（每个元素本身至少是一个长度为 1 的递增子序列）。 遍历 i 从 1 到 n-1 （ n 为数组长度）： 对于每个 i ，遍历 j 从 0 到 i-1 ： 如果 nums[j] < nums[i] ，更新 dp[i] = max(dp[i], dp[j] + 1) 。 最终结果为 dp 数组中的最大值。 5. 示例演示 以 nums = [10, 9, 2, 5, 3, 7, 101, 18] 为例： 初始化 dp = [1, 1, 1, 1, 1, 1, 1, 1] 。 i=1 （元素 9）： j=0 （10>9），不更新， dp[1]=1 。 i=2 （元素 2）： j=0,1 （10>2, 9>2），不更新， dp[2]=1 。 i=3 （元素 5）： j=2 （2<5）， dp[3]=max(1, dp[2]+1)=2 。 i=4 （元素 3）： j=2 （2<3）， dp[4]=max(1, dp[2]+1)=2 。 i=5 （元素 7）： j=2 （2<7）， dp[5]=max(1, dp[2]+1)=2 ； j=3 （5<7）， dp[5]=max(2, dp[3]+1)=3 ； j=4 （3<7）， dp[5]=max(3, dp[4]+1)=3 。 继续计算后， dp = [1,1,1,2,2,3,4,4] ，最大值为 4。 6. 复杂度分析 时间复杂度：O(n²)，需要两层循环遍历。 空间复杂度：O(n)，用于存储 dp 数组。 7. 优化思路（进阶） 可通过贪心+二分查找将时间复杂度优化到 O(n log n)，但动态规划解法是理解问题的基础。