9.＜ tag-动态规划和子序列, 子数组＞lt.718. 最长重复子数组 + lt.1143. 最长公共子序列

lt.718. 最长重复子数组

[案例需求]

[思路分析]

注意: 通常题目中, 子数组默认是连续的子序列。而求子数组这种比较适合用dp.

• 动规五步法:

1. 确定dp数组以及下标的含义:

dp[i][j]: 以下标i - 1位结尾的数组A, 和以下标j - 1为结尾的数组B, 最长重复子数组长度为dp[i][j]
特别注意： “以下标i - 1为结尾的A” 标明一定是 以A[i-1]为结尾的字符串

2. 确定递推公式

根据dp[i][j] 的定义, dp[i][j]的状态只能由dp[i - 1][j - 1] 推导出来。
即当A[i - 1] 和 B[j - 1] 相等的时候, dp[i][j] = dp[i - 1][j - 1] + 1;
根据递推公式可以看出，遍历i 和 j 要从1开始！

3. dp数组的初始化;
   

4. 确定遍历顺序
   

5. 举例推导dp数组

• 拿示例1中，A: [1,2,3,2,1]，B: [3,2,1,4,7]为例，画一个dp数组的状态变化，如下：
  

[代码实现]

class Solution {
    
    public int findLength(int[] nums1, int[] nums2) {
    
         //子序列默认不连续, 子数组默认连续
        //1. 当前状态的连续可以由前面的子序列的连续状态推出来, 所以可以用动规;
        int len1 = nums1.length;
        int len2 = nums2.length;

        //1. dp数组, dp[i] 表示i的子数组中最长的重复的连续子数组;
        // dp[i][j] 表示下标位 i - 1的数组nums1和下标为j - 1的数组nums2, 他们的公共连续重合数组为dp[i][j]
        int[][] dp = new int[len1 + 1][len2 + 1];

        //2. 递推公式
        // dp[i][j] = dp[i - 1][j - 1] + 1;

        //3. 数组的初始化
        // dp[0][0] = 0;

        //4. 确定遍历顺序, 无所谓顺序, 都是为了求两个数组的重合数据, 谁在外面都一样, 
        int res = 0;
        for(int i = 1; i < len1 + 1; i++){
    
            for(int j = 1; j < len2 + 1; j++){
    
                if(nums1[i - 1] == nums2[j - 1]){
    
                    dp[i][j] = dp[i - 1][j - 1] + 1;
                    if(dp[i][j] > res) res = dp[i][j];
                }
            }
        }    

        return res;
    }
} 

待补充, 滚动数组的做法;

lt.1143. 最长公共子序列

[案例需求]

[思路分析]

• 单纯的说让求子序列, 一般都是不连续的, 本题和上面718. 最长重复子数组 区别在于这里不要求是连续的了，但要有相对顺序，即：“ace” 是 “abcde” 的子序列，但 “aec” 不是 “abcde” 的子序列。

• 动规五部曲如下:

1. 确定dp数组及其下标含义

dp[i][j]：长度为[0, i - 1]的字符串text1与长度为[0, j - 1]的字符串text2的最长公共子序列为dp[i][j]
有同学会问：为什么要定义长度为[0, i - 1]的字符串text1，定义为长度为[0, i]的字符串text1不香么？
这样定义是为了后面代码实现方便，如果非要定义为为长度为[0, i]的字符串text1也可以，大家可以试一试！

2. 确定递推公式
   主要就是两大情况： text1[i - 1] 与 text2[j - 1]相同，text1[i - 1] 与 text2[j - 1]不相同
   a. 如果text1[i - 1] 与 text2[j - 1]相同，那么找到了一个公共元素，所以dp[i][j] = dp[i - 1][j - 1] + 1;
   b. 如果text1[i - 1] 与 text2[j - 1]不相同，那就看看text1[0, i - 2]与text2[0, j - 1]的最长公共子序列 和 text1[0, i - 1]与text2[0, j - 2]的最长公共子序列，取最大的。即：dp[i][j] = max(dp[i - 1][j], dp[i][j - 1]);

if(text1[i - 1] == text[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]);
}

3. dp数组如何初始化
   先看看dp[i][0]应该是多少呢？test1[0, i-1]和空串的最长公共子序列自然是0，所以dp[i][0] = 0;
   同理dp[0][j]也是0。其他下标都是随着递推公式逐步覆盖，初始为多少都可以，那么就统一初始为0。

4. 确定遍历顺序
   

5. 举例推导dp数组
   

[代码实现]

class Solution {
    
    public int longestCommonSubsequence(String text1, String text2) {
    
        //1. dp数组
        // dp[i][j] 表示text1和text2两个字符串在0 ~ i- 1和 0~j-1范围内的最长公共子序列;
        int len1 = text1.length();
        int len2 = text2.length();

        int[][] dp = new int[len1 + 1][len2 + 1];

        //2. 确定递推公式
        /** dp[i][j] = dp[i - 1][j - 1] + 1; dp[i][j] = dp[i - 1][j], dp[i][j - 1]; */
         //3. 初始化, 全为0

         //4. 确定遍历顺序, 从左到右, 从上到下
         for(int i = 1; i < len1 + 1; i++){
    
             for(int j = 1; j < len2 + 1; j++){
    
                 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[len1][len2];
    }
}