动态规划（三）

上一篇文章写了在动态规划中，不同路径这一类型的题目。这一次我想要来讲一讲关于最长子序列这一类型的题目，在LeetCode上这一类型的题目有：
第1143题：最长公共子序列 https://leetcode-cn.com/problems/longest-common-subsequence/
题目如下：
给定两个字符串 text1 和 text2，返回这两个字符串的最长公共子序列的长度。
一个字符串的子序列是指这样一个新的字符串：它是由原字符串在不改变字符的相对顺序的情况下删除某些字符（也可以不删除任何字符）后组成的新字符串。
例如，"ace" 是 "abcde" 的子序列，但 "aec" 不是 "abcde" 的子序列。两个字符串的「公共子序列」是这两个字符串所共同拥有的子序列。
若这两个字符串没有公共子序列，则返回 0。

其实对于算法题这个东西，是需要靠一些经验的。对于这种子序列的问题，十有八九是可以用动态规划来解决的。而做动态规划的题目是有步骤的：找到重复子问题、base case、找到状态转移方程

一、找到重复子问题

在这一道题目当中，我们要找到两个字符串的最长公共子序列（下称LCS），那其实我们只要判断两个字符串的最后一个字符是否相等。如果相等，我们只需要把两个字符串都去掉最后一个字符，然后再找到剩下字符串的LCS再加上1即可。若是不相等，那么我们只需要取text1去掉最后一个字符与text2的LCS 以及 text2去掉最后一个字符与text1的LCS之间的较大值即可。

二、base case

我们把两个字符串一个横向，一个纵向的填到一个二维数组中。但是一般来说，我们建立的数组是这样的：int[][] dp = new int[m+1][n+1]。这里加1的含义是让索引为0的行和列表示空串。如果不这样做的话，我们还需要加其他的限制条件来保证索引的有效，我们专门让索引为0的行和列表示空串，dp[0][...] 和 dp[...][0] 都应该初始化为0，这就是base case。

三、状态转移方程

对于这道题目可以先看一下下面的这一张图

image.png

找状态转移方程的过程已经在第一步中详细叙述过了，这里我就直接列出状态转移方程了。
当最后一个字符相等：dp[i+1][j+1] = dp[i][j] + 1
若不相等：dp[i + 1][j + 1] = Math.max(dp[i+1][j], dp[i][j+1]);
有了状态转移方程写代码就很容易了，代码如下：

public static int longestCommonSubsequence(String text1, String text2) {
        int m = text1.length();
        int n = text2.length();
        int[][] dp = new int[m + 1][n + 1];
        for (int i = 0; i <= m; i++) {
            for (int j = 0; j <= n; j++) {
                if (i == 0 || j == 0) {
                    dp[i][j] = 0;
                    continue;
                }
                if (text1.charAt(i-1) == text2.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];
    }

这一类型的题目还有第718题最长重复子数组 https://leetcode-cn.com/problems/maximum-length-of-repeated-subarray/ 题目如下：
给两个整数数组 A 和 B ，返回两个数组中公共的、长度最长的子数组的长度。
输入：
A: [1,2,3,2,1]
B: [3,2,1,4,7]
输出：3
解释：
长度最长的公共子数组是 [3, 2, 1] 。

其实这类最长子序列的题目做法都差不多。就从后面开始找起。若两数组的最后一个元素不相等，那不用说了，公共子数组肯定不包括他俩。若是相等，那么就把最后一个元素都去掉，看前面的数组能给他们提供多长的子序列。这题和上一题的区别就在于这里的子数组是要连续的。因此当最后一个元素不相等的时候，dp[i][j]就要等于0了。这里的dp数组存储的就是以 A[i], B[j] 结尾的两个数组中公共的、长度最长的子数组的长度。
状态转移方程也很容易得到：如果 A[i] == B[j]，dp[i][j] = dp[i - 1][j - 1] + 1，否则，dp[i][j] = 0。
还有一点，与上一题不同，这一题需要再循环的过程中记录最大值。
代码如下：

public static int findLength(int[] A, int[] B) {
        int m = A.length;
        int n = B.length;
        int[][] dp = new int[m + 1][n + 1];
        int ans = 0;
        for (int i = 1; i <= m; i++) {
            for (int j = 1; j <= n; j++) {
                dp[i][j] = A[i - 1] == B[j - 1] ? dp[i - 1][j - 1] + 1 : 0;
                ans = Math.max(ans, dp[i][j]);
            }
        }
        return ans;
    }

还有Leetcode的第1035题：不相交的线 https://leetcodecn.com/problems/uncrossed-lines/description/

题目套路是一样的，其实就是求最大不连续的子序列啦，贴一下代码

public static int maxUncrossedLines(int[] A, int[] B) {
        int m = A.length;
        int 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++) {
                dp[i][j] = A[i - 1] == B[j - 1] ? dp[i - 1][j - 1] + 1 : Math.max(dp[i][j - 1], dp[i - 1][j]);
            }
        }
        return dp[m][n];
    }

好了，以上就是我对于动态规划中最大公共子序列这类题目的一些理解，本人才疏学浅，如有不对，还望批评指正。