动态规划：最长递增子序列（LIS）问题

字数 3143 2025-12-06 10:33:14

动态规划：最长递增子序列（LIS）问题

题目描述
最长递增子序列（Longest Increasing Subsequence, LIS）是一个经典的动态规划问题。给定一个长度为 n 的整数数组 nums，找到其中最长的严格递增子序列的长度。子序列是指从原数组中删除一些元素（也可以不删除）后，剩余元素保持原有顺序形成的序列，不要求连续。递增是指严格递增，即对于子序列中的任意两个相邻元素，后一个元素必须大于前一个元素。

例如，对于数组 nums = [10, 9, 2, 5, 3, 7, 101, 18]，其最长递增子序列之一是 [2, 5, 7, 101] 或 [2, 3, 7, 101]，长度为 4。

解题过程循序渐进讲解

第一步：理解问题与明确目标
我们要求的是最长递增子序列的长度，而不是具体的子序列内容（但算法思想通常也能回溯得到序列）。注意是“子序列”，不是“子数组”，元素可以不连续。目标是设计一个高效的算法计算这个最大长度。

第二步：暴力解法思考
最直观的方法是枚举所有可能的子序列，检查每个子序列是否递增，然后记录最长的长度。一个长度为 n 的数组有 2^n 个子序列（每个元素选或不选），检查每个子序列是否递增需要 O(m) 时间（m 为子序列长度）。总时间复杂度是 O(2^n * n)，指数级，完全不可接受。我们需要更优的解法。

第三步：动态规划思路推导
动态规划的核心是将原问题分解为子问题，并存储子问题的解，避免重复计算。对于 LIS 问题，一个常见的定义是：

定义 dp[i] 为：以 nums[i] 结尾的最长递增子序列的长度。

为什么这么定义？因为当我们考虑整个数组的最长递增子序列时，它一定是以某个元素结尾的。如果我们能计算出每个位置 i 的 dp[i]，那么整个数组的 LIS 长度就是 max(dp[0], dp[1], ..., dp[n-1])。

第四步：状态转移方程推导
现在思考如何计算 dp[i]。
对于以 nums[i] 结尾的递增子序列，它的前一个元素可能是 nums[0] 到 nums[i-1] 中的某一个 nums[j]（j < i），且必须满足 nums[j] < nums[i]。
如果存在这样的 j，那么 dp[i] 就可以在 dp[j] 的基础上加 1（即在以 nums[j] 结尾的递增子序列后面加上 nums[i]）。
如果没有这样的 j（即 nums[i] 比前面所有元素都小），那么以 nums[i] 结尾的递增子序列就只包含它自己，长度为 1。

因此，状态转移方程为：
dp[i] = 1 + max{ dp[j] }，其中 0 ≤ j < i 且 nums[j] < nums[i]。
如果不存在这样的 j，则 dp[i] = 1。

用数学公式表达：
dp[i] = max(1, max{ dp[j] + 1 | 0 ≤ j < i 且 nums[j] < nums[i] })

第五步：算法实现步骤

初始化一个长度为 n 的数组 dp，所有元素设为 1（因为每个元素自身至少可以构成长度为 1 的递增子序列）。
从左到右遍历 i 从 0 到 n-1：
对于每个 i，遍历 j 从 0 到 i-1：
如果 nums[j] < nums[i]，则更新 dp[i] = max(dp[i], dp[j] + 1)。
遍历结束后，dp 数组中的最大值就是整个数组的最长递增子序列的长度。

时间复杂度：外层循环 O(n)，内层循环 O(i)，总时间复杂度 O(n^2)。
空间复杂度：O(n) 用于存储 dp 数组。

第六步：举例演算
以 nums = [10, 9, 2, 5, 3, 7, 101, 18] 为例：

i=0: nums[0]=10，前面没有元素，dp[0]=1。
i=1: nums[1]=9，前面元素 10 大于 9，不满足递增，dp[1]=1。
i=2: nums[2]=2，前面元素 10 和 9 都大于 2，dp[2]=1。
i=3: nums[3]=5，前面比 5 小的有 2（dp[2]=1），所以 dp[3]=dp[2]+1=2。
i=4: nums[4]=3，前面比 3 小的有 2（dp[2]=1），所以 dp[4]=dp[2]+1=2。
i=5: nums[5]=7，前面比 7 小的有 2（dp=1）、5（dp=2）、3（dp=2），取最大 dp 值 2 加 1，dp[5]=3。
i=6: nums[6]=101，前面比 101 小的有 10、9、2、5、3、7，其中最大 dp 值是 7 对应的 dp[5]=3，所以 dp[6]=4。
i=7: nums[7]=18，前面比 18 小的有 10、9、2、5、3、7，其中最大 dp 值是 7 对应的 dp[5]=3，所以 dp[7]=4。
dp 数组为 [1,1,1,2,2,3,4,4]，最大值为 4，即 LIS 长度为 4。

第七步：优化到 O(n log n) 的贪心+二分法
O(n^2) 的解法在 n 较大时仍可能较慢。我们可以进一步优化到 O(n log n)。
思路是维护一个数组 tail，其中 tail[k] 表示长度为 k+1 的递增子序列的最小末尾元素。tail 数组本身是递增的（可以通过反证法证明）。
遍历 nums 每个元素 x：

如果 x 大于 tail 中的所有元素（即大于最后一个元素），则将 x 加入 tail 末尾，表示我们找到了一个更长的递增子序列。
否则，在 tail 数组中二分查找第一个大于等于 x 的位置，用 x 替换该位置上的元素。这表示我们找到了一个更优的、长度为 (index+1) 的递增子序列的末尾（更小）。
遍历结束后，tail 的长度就是 LIS 的长度。

第八步：O(n log n) 算法举例
nums = [10, 9, 2, 5, 3, 7, 101, 18]

初始 tail = []
x=10: tail 空，直接加入 → tail = [10]
x=9: 二分查找 tail 中第一个 ≥9 的位置是 0（值 10），替换 → tail = [9]
x=2: 二分查找第一个 ≥2 的位置 0（值 9），替换 → tail = [2]
x=5: 5 > tail 最后一个元素 2，加入 → tail = [2,5]
x=3: 二分查找第一个 ≥3 的位置 1（值 5），替换 → tail = [2,3]
x=7: 7 > 3，加入 → tail = [2,3,7]
x=101: 101 > 7，加入 → tail = [2,3,7,101]
x=18: 二分查找第一个 ≥18 的位置 3（值 101），替换 → tail = [2,3,7,18]
tail 长度为 4，即 LIS 长度为 4。

注意：tail 数组不一定是最优的 LIS 序列本身，但它的长度是准确的 LIS 长度。

第九步：总结
最长递增子序列问题有两种主要解法：

动态规划 O(n^2)：定义 dp[i] 为以 i 结尾的 LIS 长度，状态转移基于之前所有小于当前元素的 dp 值。
贪心+二分 O(n log n)：维护一个最小末尾数组，通过二分查找更新，得到 LIS 长度。
后者是更优的算法，适用于 n 较大的场景。

动态规划：最长递增子序列（LIS）问题题目描述最长递增子序列（Longest Increasing Subsequence, LIS）是一个经典的动态规划问题。给定一个长度为 n 的整数数组 nums，找到其中最长的严格递增子序列的长度。子序列是指从原数组中删除一些元素（也可以不删除）后，剩余元素保持原有顺序形成的序列，不要求连续。递增是指严格递增，即对于子序列中的任意两个相邻元素，后一个元素必须大于前一个元素。例如，对于数组 nums = [ 10, 9, 2, 5, 3, 7, 101, 18]，其最长递增子序列之一是 [ 2, 5, 7, 101] 或 [ 2, 3, 7, 101 ]，长度为 4。解题过程循序渐进讲解第一步：理解问题与明确目标我们要求的是最长递增子序列的长度，而不是具体的子序列内容（但算法思想通常也能回溯得到序列）。注意是“子序列”，不是“子数组”，元素可以不连续。目标是设计一个高效的算法计算这个最大长度。第二步：暴力解法思考最直观的方法是枚举所有可能的子序列，检查每个子序列是否递增，然后记录最长的长度。一个长度为 n 的数组有 2^n 个子序列（每个元素选或不选），检查每个子序列是否递增需要 O(m) 时间（m 为子序列长度）。总时间复杂度是 O(2^n * n)，指数级，完全不可接受。我们需要更优的解法。第三步：动态规划思路推导动态规划的核心是将原问题分解为子问题，并存储子问题的解，避免重复计算。对于 LIS 问题，一个常见的定义是：定义 dp[ i] 为：以 nums[ i ] 结尾的最长递增子序列的长度。为什么这么定义？因为当我们考虑整个数组的最长递增子序列时，它一定是以某个元素结尾的。如果我们能计算出每个位置 i 的 dp[ i]，那么整个数组的 LIS 长度就是 max(dp[ 0], dp[ 1], ..., dp[ n-1 ])。第四步：状态转移方程推导现在思考如何计算 dp[ i ]。对于以 nums[ i] 结尾的递增子序列，它的前一个元素可能是 nums[ 0] 到 nums[ i-1] 中的某一个 nums[ j]（j < i），且必须满足 nums[ j] < nums[ i ]。如果存在这样的 j，那么 dp[ i] 就可以在 dp[ j] 的基础上加 1（即在以 nums[ j] 结尾的递增子序列后面加上 nums[ i ]）。如果没有这样的 j（即 nums[ i] 比前面所有元素都小），那么以 nums[ i ] 结尾的递增子序列就只包含它自己，长度为 1。因此，状态转移方程为： dp[ i] = 1 + max{ dp[ j] }，其中 0 ≤ j < i 且 nums[ j] < nums[ i ]。如果不存在这样的 j，则 dp[ i ] = 1。用数学公式表达： dp[ i] = max(1, max{ dp[ j] + 1 | 0 ≤ j < i 且 nums[ j] < nums[ i ] }) 第五步：算法实现步骤初始化一个长度为 n 的数组 dp，所有元素设为 1（因为每个元素自身至少可以构成长度为 1 的递增子序列）。从左到右遍历 i 从 0 到 n-1：对于每个 i，遍历 j 从 0 到 i-1：如果 nums[ j] < nums[ i]，则更新 dp[ i] = max(dp[ i], dp[ j ] + 1)。遍历结束后，dp 数组中的最大值就是整个数组的最长递增子序列的长度。时间复杂度：外层循环 O(n)，内层循环 O(i)，总时间复杂度 O(n^2)。空间复杂度：O(n) 用于存储 dp 数组。第六步：举例演算以 nums = [ 10, 9, 2, 5, 3, 7, 101, 18 ] 为例： i=0: nums[ 0]=10，前面没有元素，dp[ 0 ]=1。 i=1: nums[ 1]=9，前面元素 10 大于 9，不满足递增，dp[ 1 ]=1。 i=2: nums[ 2]=2，前面元素 10 和 9 都大于 2，dp[ 2 ]=1。 i=3: nums[ 3]=5，前面比 5 小的有 2（dp[ 2]=1），所以 dp[ 3]=dp[ 2 ]+1=2。 i=4: nums[ 4]=3，前面比 3 小的有 2（dp[ 2]=1），所以 dp[ 4]=dp[ 2 ]+1=2。 i=5: nums[ 5]=7，前面比 7 小的有 2（dp=1）、5（dp=2）、3（dp=2），取最大 dp 值 2 加 1，dp[ 5 ]=3。 i=6: nums[ 6]=101，前面比 101 小的有 10、9、2、5、3、7，其中最大 dp 值是 7 对应的 dp[ 5]=3，所以 dp[ 6 ]=4。 i=7: nums[ 7]=18，前面比 18 小的有 10、9、2、5、3、7，其中最大 dp 值是 7 对应的 dp[ 5]=3，所以 dp[ 7 ]=4。 dp 数组为 [ 1,1,1,2,2,3,4,4 ]，最大值为 4，即 LIS 长度为 4。第七步：优化到 O(n log n) 的贪心+二分法 O(n^2) 的解法在 n 较大时仍可能较慢。我们可以进一步优化到 O(n log n)。思路是维护一个数组 tail，其中 tail[ k ] 表示长度为 k+1 的递增子序列的最小末尾元素。tail 数组本身是递增的（可以通过反证法证明）。遍历 nums 每个元素 x：如果 x 大于 tail 中的所有元素（即大于最后一个元素），则将 x 加入 tail 末尾，表示我们找到了一个更长的递增子序列。否则，在 tail 数组中二分查找第一个大于等于 x 的位置，用 x 替换该位置上的元素。这表示我们找到了一个更优的、长度为 (index+1) 的递增子序列的末尾（更小）。遍历结束后，tail 的长度就是 LIS 的长度。第八步：O(n log n) 算法举例 nums = [ 10, 9, 2, 5, 3, 7, 101, 18 ] 初始 tail = [ ] x=10: tail 空，直接加入 → tail = [ 10 ] x=9: 二分查找 tail 中第一个 ≥9 的位置是 0（值 10），替换 → tail = [ 9 ] x=2: 二分查找第一个 ≥2 的位置 0（值 9），替换 → tail = [ 2 ] x=5: 5 > tail 最后一个元素 2，加入 → tail = [ 2,5 ] x=3: 二分查找第一个 ≥3 的位置 1（值 5），替换 → tail = [ 2,3 ] x=7: 7 > 3，加入 → tail = [ 2,3,7 ] x=101: 101 > 7，加入 → tail = [ 2,3,7,101 ] x=18: 二分查找第一个 ≥18 的位置 3（值 101），替换 → tail = [ 2,3,7,18 ] tail 长度为 4，即 LIS 长度为 4。注意：tail 数组不一定是最优的 LIS 序列本身，但它的长度是准确的 LIS 长度。第九步：总结最长递增子序列问题有两种主要解法：动态规划 O(n^2)：定义 dp[ i ] 为以 i 结尾的 LIS 长度，状态转移基于之前所有小于当前元素的 dp 值。贪心+二分 O(n log n)：维护一个最小末尾数组，通过二分查找更新，得到 LIS 长度。后者是更优的算法，适用于 n 较大的场景。