线性 DP 与子序列 DP：从位置依赖到双字符串状态

这部分知识我前后看过不止一次。刚接触“线性 DP 与子序列 DP：从位置依赖到双字符串状态”时，线性 DP 还能顺着位置往前推，到了子序列和双字符串问题，我就经常把下标含义和空串边界写乱。等我回头从问题本身出发，而不是从模板出发，很多原来零散的规则才慢慢连在一起。下面按我自己的理解过程展开。

动态规划前面已经讲过基本状态设计，这篇继续拆最常见的两类：线性 DP 和子序列 DP。它们是面试中最常出现、也最容易从暴力递归优化过来的题型。

DP 题型地图

动态规划题型地图

图：DP 的分类来自状态依赖，而不是题目名字

线性 DP

线性 DP 通常按位置 i 推进，当前状态依赖前面若干位置。

典型例子是打家劫舍：

int rob(int[] nums) {
    int prev2 = 0;
    int prev1 = 0;
    for (int x : nums) {
        int cur = Math.max(prev1, prev2 + x);
        prev2 = prev1;
        prev1 = cur;
    }
    return prev1;
}

状态含义：

prev1：处理到前一个房子的最大金额。
prev2：处理到前两个房子的最大金额。
当前选择：偷当前房子，或者不偷。

最大子数组和

int maxSubArray(int[] nums) {
    int best = nums[0];
    int cur = nums[0];
    for (int i = 1; i < nums.length; i++) {
        cur = Math.max(nums[i], cur + nums[i]);
        best = Math.max(best, cur);
    }
    return best;
}

cur 表示“必须以当前位置结尾的最大子数组和”。这个状态定义非常关键，如果只说“前 i 个最大和”，转移就会不清楚。

子序列 DP

子序列问题通常有两个特征：

可以不连续。
保持相对顺序。

最长递增子序列的 O(n²) 写法：

int lengthOfLIS(int[] nums) {
    int n = nums.length;
    int[] dp = new int[n];
    Arrays.fill(dp, 1);
    int ans = 1;
    for (int i = 0; i < n; i++) {
        for (int 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;
}

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

两个字符串的 DP

最长公共子序列：

int longestCommonSubsequence(String a, String b) {
    int m = a.length(), n = b.length();
    int[][] dp = new int[m + 1][n + 1];
    for (int i = 1; i <= m; i++) {
        for (int j = 1; j <= n; j++) {
            if (a.charAt(i - 1) == b.charAt(j - 1)) {
                dp[i][j] = dp[i - 1][j - 1] + 1;
            } else {
                dp[i][j] = Math.max(dp[i - 1][j], dp[i][j - 1]);
            }
        }
    }
    return dp[m][n];
}

两个字符串 DP 通常用 dp[i][j] 表示 a 的前 i 个字符和 b 的前 j 个字符之间的答案。

我的分析

DP 最忌讳直接背转移方程。我的习惯是先说一句人话：dp[i] 或 dp[i][j] 到底代表什么，而且必须说明“是否包含当前位置”。这句话说不清，代码大概率会乱。

面试题

最大子数组和的 dp[i] 为什么要定义成“以 i 结尾”？
子数组和子序列有什么区别？
LIS 的 O(n²) 解法如何优化到 O(n log n)？
LCS 为什么需要二维 DP？
DP 状态压缩的前提是什么？