在上两篇文章中，我们将 暴力递归 逐步修改成为 动态规划 ，并介绍了有严格 dp表依赖 和无表依赖结构的解题方法。其中，前篇文章中的纸牌博弈问题属于 [L , R]上范围尝试模型。该模型给定一个范围，在该范围上进行尝试，套路就是 思考 [L ,R] 两端该如何取舍。

本篇文章我们学习一个新的模型： 样本对应模型，该模型的套路就是 以结尾位置为出发点，思考两个样本的结尾都会产生哪些可能性 。

力扣1143：最长公共子序列

给定两个字符串 text1 和 text2，返回这两个字符串的最长 公共子序列 的长度。如果不存在 公共子序列 ，返回 0 。

一个字符串的 子序列 是指这样一个新的字符串：它是由原字符串在不改变字符的相对顺序的情况下删除某些字符（也可以不删除任何字符）后组成的新字符串。

两个字符串的 公共子序列 是这两个字符串所共同拥有的子序列。

示例 1：

输入: text1 = “abcde”, text2 = “ace”

*输出：*3

*解释：*最长公共子序列是 “ace” ，它的长度为 3 。

示例 2:

*输入：*text1 = “abc”, text2 = “def”

*输出：*0

*解释：*两个字符串没有公共子序列，返回 0 。

首先我们依然采用最朴素的 暴力递归 来思考这道题目。

递归的准备

定义递归函数的功能： 返回 str1 中 [0...i] ，str2 中 [0...j] 范围上两个字符串的最长公共子序列。

思考递归需要的参数： str1, str2 两个字符串，分别要比较的范围 i, j。

明确递归的边界条件： 当两个字符串长度均为 1 时：若两个字符相同返回 1 ，不同返回 0 。

思路

这道题就是典型的 样本对应模型 ，因此，递归就可以按照 两个样本的结尾都会产生哪些可能性 的思路来划分情况：

• 公共子序列 既不以 str1 结尾，也不以 str2 结尾；
• 公共子序列 以 str1 结尾，不以 str2 结尾；
• 公共子序列 不以 str1 结尾，以 str2 结尾；
• 公共子序列 既以 str1 结尾，也以 str2 结尾。

因为要求 最长 子序列，因此要返回这四种情况当中的最大值。

代码

public static int longestCommonSubsequence(String s1, String s2) {
    if (s1 == null || s2 == null || s1.length() == 0 || s2.length() == 0) {
        return 0;
    }
    char[] str1 = s1.toCharArray();
    char[] str2 = s2.toCharArray();
    return process(str1, str2, str1.length - 1, str2.length - 1);
}

public static int process(char[] str1, char[] str2, int i, int j) {
    if (i == 0 && j == 0) {
        return str1[i] == str2[j] ? 1 : 0;
    } else if (i == 0) {
        return str1[i] == str2[j] ? 1 : process(str1, str2, i, j - 1);
    } else if (j == 0) {
        return str1[i] == str2[j] ? 1 : process(str1, str2, i - 1, j);
    } else {
        int p1 = process(str1, str2, i - 1, j - 1);
        int p2 = process(str1, str2, i, j - 1);
        int p3 = process(str1, str2, i - 1, j);
        int p4 = str1[i] == str2[j] ? 1 + process(str1, str2, i - 1, j - 1) : 0;
        return Math.max(Math.max(p1, p2), Math.max(p3, p4));
    }
}

代码解释

因为递归调用中使用到了 i-1 , j-1，因此需要做边界处理。例如：当str1 中只剩下一个字符时，若与 str2 最后一个字符相等即找到了此时最长子序列，否则排除掉 str2 的最后一个字符继续递归寻找。

---

写出该暴力版的递归之后发现，最终要求的是最大值，因此其实 p1 的情况是一定不会比 p2 ，p3 的情况返回值要大，所以可以减少一次递归的调用，做个小小的优化。

动态规划版

public static int longestCommonSubsequence(String s1, String s2) {
    if (s1 == null || s2 == null || s1.length() == 0 || s2.length() == 0) {
        return 0;
    }
    char[] str1 = s1.toCharArray();
    char[] str2 = s2.toCharArray();
    int N = str1.length;
    int M = str2.length;
    int[][] dp = new int[N][M];
    // 处理 str1 和 str2 均剩下一个字符的情况
    dp[0][0] = 1;
    // 处理 str1 剩下一个字符的情况 
    for (int j = 1; j < M; j++) {
        dp[0][j] = str1[0] == str2[j] ? 1 : dp[0][j - 1];
    }
    // 处理 str2 剩下一个字符的情况 
    for (int i = 1; i < N; i++) {
        dp[i][0] = str1[i] == str2[0] ? 1 : dp[i - 1][0];
    }
    // str1 str2 均有多个字符的情况
    for (int i = 1; i < N; i++) {
        for (int j = 1; j < M; j++) {
            int p1 = dp[i][j - 1];
            int p2 = dp[i - 1][j];
            int p3 = str1[i] == str2[j] ? 1 + dp[i - 1][j - 1] : 0;
            dp[i][j] = Math.max(Math.max(p1, p2), p3);
        }
    }
    return dp[N - 1][M - 1];
}

代码解释

根据递归函数修改出这套动态规划版代码就非常容易了。

以 str1 = “abcde”, str2 = “ace” 为例

可变的参数有两个：str1 和 str2 判断长度范围的 i 和 j。因此，需要设置一个二维的 dp 表数组，由于 i, j 的取值范围从 0 开始到字符串长度减一，因此数组大小设置为 dp[N][M] 。

递归代码 i==0 && j==0 可知，初始只有 dp[0][0] 的值为 1 。

当 i == 0 或 j == 0时，只依赖左侧或上侧的数值。

当 str1 和 str2 均有多个字符时，会依赖 左，上，左上 三个地方的 最大值。

由递归调用函数 process(str1, str2, str1.length - 1, str2.length - 1) 可知，最终要求的是 dp[N - 1][M - 1] 的值 3。

总结

本篇文章我们学习了一个新的分析模型 —— 样本对应模型 。该模型的套路就是： 以结尾位置为出发点，思考两个样本的结尾都会产生哪些可能性 。

下篇文章我们继续学习类似的题型，但分析模型可以完全不一样哦，敬请期待！

~ 点赞 ~ 关注 ~ 不迷路 ~！！！

------------- 往期回顾 -------------
【算法 - 动态规划】力扣 691. 贴纸拼词
【算法 - 动态规划】原来写出动态规划如此简单！
【算法 - 动态规划】从零开始学动态规划！（总纲）
【堆 - 专题】“加强堆” 解决 TopK 问题！
AC 此题，链表无敌！！！