忍者算法

Appearance

最长递增子序列：从具体到抽象的动态规划之旅 ​

在算法面试中,最长递增子序列(Longest Increasing Subsequence, LIS)是一道经典的动态规划题目。这篇文章将通过具体的例子,带你一步步理解这个问题的解决思路。

🎯 问题描述 ​

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

注意:子序列不要求连续,但要保持原始顺序。

例如:

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

💡 从具体例子开始理解 ​

让我们通过一个更简单的例子来逐步理解这个问题:

nums = [3,1,4,5,2]

如果我们要手动找出这个数组的最长递增子序列,我们会怎么思考?

  1. 从第一个数字 3 开始:

    • [3] 是一个长度为1的递增子序列
    • 后面比3大的数有: 4,5,所以可以得到 [3,4,5]

  2. 从第二个数字 1 开始:

    • [1] 是一个长度为1的递增子序列
    • 后面比1大的数有: 4,5,2
    • 可以得到 [1,4,5] 或 [1,2]

  3. 从第三个数字 4 开始:

    • [4] 是一个长度为1的递增子序列
    • 后面比4大的只有5,所以可以得到 [4,5]

... 以此类推

通过这个例子,我们发现一个关键点:对于每个位置i,我们需要知道以nums[i]结尾的最长递增子序列的长度。

🔍 发现状态定义 ​

这个发现直接引导我们找到了动态规划的状态定义:

dp[i] 表示: 以 nums[i] 结尾的最长递增子序列的长度。

让我们通过例子来理解这个状态定义:

nums = [3,1,4,5,2]
初始化: dp[i] = 1 (因为每个数字本身就是长度为1的子序列)
dp = [1,1,1,1,1]

🎨 推导状态转移方程 ​

关键问题是:如何计算dp[i]?

还是用具体例子来思考: 当我们要计算 dp[3]（也就是以 5 结尾的最长递增子序列长度）时:

  1. 看前面所有比5小的数字:
    • 3 < 5, 可以接在3后面,此时长度为dp[0] + 1 = 2
    • 1 < 5, 可以接在1后面,此时长度为dp[1] + 1 = 2
    • 4 < 5, 可以接在4后面,此时长度为dp[2] + 1 = 2

所以dp[3] = max(dp[j] + 1),其中j < i且nums[j] < nums[i]

完整的状态转移过程:

nums = [3,1,4,5,2]
dp[0] = 1                     dp = [1,1,1,1,1]
dp[1] = 1                     dp = [1,1,1,1,1]
dp[2] = max(dp[1]+1) = 2     dp = [1,1,2,1,1]
dp[3] = max(dp[2]+1) = 3     dp = [1,1,2,3,1]
dp[4] = max(dp[1]+1) = 2     dp = [1,1,2,3,2]

📝 代码实现 ​

java
class Solution {
    public int lengthOfLIS(int[] nums) {
        if (nums == null || nums.length == 0) return 0;
        
        // dp[i]表示以nums[i]结尾的最长递增子序列的长度
        int[] dp = new int[nums.length];
        // 初始化:每个数字本身就是长度为1的子序列
        Arrays.fill(dp, 1);
        
        // 最终的结果(全局最大值)
        int maxLen = 1;
        
        // 遍历每个位置,计算以该位置结尾的LIS长度
        for (int i = 1; i < nums.length; i++) {
            // 查看i之前的所有数字
            for (int j = 0; j < i; j++) {
                // 如果当前数字大于之前的数字,可以接在该数字后面形成更长的递增子序列
                if (nums[i] > nums[j]) {
                    dp[i] = Math.max(dp[i], dp[j] + 1);
                }
            }
            // 更新全局最大长度
            maxLen = Math.max(maxLen, dp[i]);
        }
        
        return maxLen;
    }
}

🎯 复杂度分析 ​

  • 时间复杂度: O(n²),其中n是数组长度
  • 空间复杂度: O(n),用于存储dp数组

💡 进阶思考 ​

这个O(n²)的解法是最优解吗?

实际上,我们可以用二分查找将时间复杂度优化到O(nlogn)。具体思路是维护一个递增数组,表示到目前为止找到的最长递增子序列。这个优化留给读者思考,我们将在下一篇文章中详细讨论。

🎓 面试指南 ​

遇到这类问题时,建议按以下步骤思考:

  1. 从小规模例子开始,手动模拟找出递增子序列
  2. 思考对于每个位置,我们需要知道什么信息
  3. 将这个信息转化为状态定义
  4. 通过具体例子推导状态转移方程
  5. 考虑边界情况和初始化
  6. 最后考虑优化空间

记住,动态规划的难点往往在于找到正确的状态定义。通过具体例子来思考,往往能帮助我们更直观地理解问题。

作者：忍者算法
公众号：忍者算法

希望这篇文章能帮助你深入理解最长递增子序列问题。如果你有任何问题,欢迎在评论区讨论！

#算法面试 #LeetCode #动态规划 #最长递增子序列