最长递增子序列

线性 DP 经典题：练习“以 i 结尾”的状态设计与枚举最后一个选谁。

#algorithm #snippet #growing #leetcode #dp

[!info] related notes 动态规划线性 DP

最长递增子序列

题目链接：https://leetcode.cn/problems/longest-increasing-subsequence/

状态

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

转移

枚举 j < i：

if nums[j] < nums[i]
    dp[i] = max(dp[i], dp[j] + 1)

样例

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

答案是 4，例如子序列 [2, 3, 7, 101]。

JavaScript

var lengthOfLIS = function(nums) {
    const n = nums.length;
    const dp = new Array(n).fill(1);
    let ans = 1;

    for (let i = 0; i < n; i++) {
        for (let j = 0; j < i; j++) {
            if (nums[j] < nums[i]) {
                dp[i] = Math.max(dp[i], dp[j] + 1);
            }
        }
        ans = Math.max(ans, dp[i]);
    }

    return ans;
};

易错点

这题是“以 i 结尾”，不是“前 i 个元素”
dp[i] 初始值是 1，因为每个元素自己都能构成长度为 1 的子序列