9. < tag dynamic programming and subsequence, subarray> lt.718. Longest repeated subarray + lt.1143. Longest common subsequence

lt.718. Longest repeating subarray

[ Case needs ]

[ Thought analysis ]

Be careful : Usually in the title , The subarray defaults to Continuous subsequences . And the subarray is more suitable for dp.

• Five steps of dynamic rule :

1. determine dp The meaning of arrays and subscripts :

dp[i][j]: By subscript i - 1 Bit terminated array A, And the following j - 1 An array ending with B, The longest repeating subarray length is dp[i][j]
Particular attention ： “ By subscript i - 1 For the end of A” Mark it must be With A[i-1] String ending with

2. Determine the recurrence formula

according to dp[i][j] The definition of , dp[i][j] The state of can only be determined by dp[i - 1][j - 1] derived .
When A[i - 1] and B[j - 1] On equal terms , dp[i][j] = dp[i - 1][j - 1] + 1;
According to the recurrence formula, we can see , Traverse i and j From you to 1 Start ！

3. dp Initialization of an array ;
   

4. Determine the traversal order
   

5. Give an example to deduce dp Array

• Take for example 1 in ,A: [1,2,3,2,1],B: [3,2,1,4,7] For example , Draw a picture dp The state of the array changes , as follows ：
  

[ Code implementation ]

class Solution {
    
    public int findLength(int[] nums1, int[] nums2) {
    
         // Subsequences are discontinuous by default ,  Subarray is continuous by default 
        //1.  The continuity of the current state can be deduced from the continuous state of the preceding subsequence ,  So you can use a dynamic gauge ;
        int len1 = nums1.length;
        int len2 = nums2.length;

        //1. dp Array , dp[i]  Express i The longest repeated continuous subarray in the subarray of ;
        // dp[i][j]  Indicates subscript  i - 1 Array of nums1 And the subscript is j - 1 Array of nums2,  Their common continuous coincidence array is dp[i][j]
        int[][] dp = new int[len1 + 1][len2 + 1];

        //2.  The recursive formula 
        // dp[i][j] = dp[i - 1][j - 1] + 1;

        //3.  Initialization of an array 
        // dp[0][0] = 0;

        //4.  Determine the traversal order ,  It doesn't matter the order ,  Is to find the coincidence data of two arrays ,  Everyone is the same outside , 
        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;
    }
} 

To be added , The practice of scrolling arrays ;

lt.1143. Longest common subsequence

[ Case needs ]

[ Thought analysis ]

• Simply put, let's find subsequences , Generally, it is discontinuous , This question and the above 718. Longest repeating subarray The difference is that it is not required to be continuous , But in relative order , namely ：“ace” yes “abcde” The subsequence , but “aec” No “abcde” The subsequence .

• The five parts of dynamic rule are as follows :

1. determine dp Array and its subscript meaning

dp[i][j]： The length is [0, i - 1] String text1 And length [0, j - 1] String text2 The longest common subsequence of is dp[i][j]
Some students will ask ： Why define the length as [0, i - 1] String text1, Defined as a length of [0, i] String text1 Is it not fragrant ？
This definition is for the convenience of later code implementation , If you have to define the length as [0, i] String text1 It's fine too , You can try ！

2. Determine the recurrence formula
   There are mainly two situations ： text1[i - 1] And text2[j - 1] identical ,text1[i - 1] And text2[j - 1] inequality
   a. If text1[i - 1] And text2[j - 1] identical , So we found a common element , therefore dp[i][j] = dp[i - 1][j - 1] + 1;
   b. If text1[i - 1] And text2[j - 1] inequality , Then look at it. text1[0, i - 2] And text2[0, j - 1] The longest common subsequence of and text1[0, i - 1] And text2[0, j - 2] The longest common subsequence of , Take one of the biggest . namely ：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 How to initialize an array
   Have a look first dp[i][0] How much should it be ？test1[0, i-1] And the longest common subsequence of empty string is naturally 0, therefore dp[i][0] = 0;
   Empathy dp[0][j] It's also 0. Other subscripts are gradually covered with the recursive formula , The initial value can be as much as , Then unify the initial 0.

4. Determine the traversal order
   

5. Give an example to deduce dp Array
   

[ Code implementation ]

class Solution {
    
    public int longestCommonSubsequence(String text1, String text2) {
    
        //1. dp Array 
        // dp[i][j]  Express text1 and text2 Two strings in 0 ~ i- 1 and  0~j-1 The longest common subsequence in the range ;
        int len1 = text1.length();
        int len2 = text2.length();

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

        //2.  Determine the recurrence formula 
        /** dp[i][j] = dp[i - 1][j - 1] + 1; dp[i][j] = dp[i - 1][j], dp[i][j - 1]; */
         //3.  initialization ,  All for 0

         //4.  Determine the traversal order ,  From left to right ,  From top to bottom 
         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];
    }
}