10. < tag dynamic programming and subsequence, subarray> lt.53. maximum subarray and + lt.392. Judge subsequence DBC

lt.53. Maximum subarray and

[ Case needs ]

[ Train of thought analysis 1 , The law of greed ]

I'm greedy , I want to accumulate from scratch , Then use a variable to record the maximum value of each accumulation , Anyway, I only care about the final maximum sum .

But what we should notice is , The array contains negative numbers ! If we accumulate negative numbers, we get a negative number , Then the cumulative variable should be set to 0, Restart accumulation .

The starting position of red is greedy. Every time you take count When it's positive , Start the statistics of an interval .

[ Code implementation ]

class Solution {
    
    public int maxSubArray(int[] nums) {
    
        int res = Integer.MIN_VALUE;
        int len = nums.length;
        int sum = 0;
        for(int i = 0; i < len; i++){
    
            sum += nums[i];
            res = Math.max(res, sum);

            if(sum < 0)sum = 0;
        }
        return res;
    }
}

[ Train of thought analysis II , Dynamic programming ]

1. determine dp[i] And what it means

dp[i]: Include Subscripts i The previous maximum continuous subsequence sum is dp[i].

2. The recursive formula :

dp[i] There are only two directions to push out :
Pay attention , nums[i] In any case, it should be added to dp Medium , So I didn't say no nums[i] And join nums[i] This saying ( Even if nums[i] It's a negative number );

1. nums[i] + dp[ i - 1], namely nums[i] Add the current continuous subsequence and
2. nums[i]. That is, calculate the sum of the current continuous subsequences from scratch ;
   It must be the largest , therefore dp[i] = max(dp[i - 1] + nums[i], nums[i]);

3. initialization

It can be seen from the recurrence formula dp[i] It depends on dp[i - 1] The state of ,dp[0] Is the basis of the recursive formula .
dp[0] How much should it be ?
according to dp[i] The definition of , Obviously dp[0] Should be nums[0] namely dp[0] = nums[0].

4. Determine the traversal order

In recursive formula dp[i] Depend on dp[i - 1] The state of , You need to traverse from front to back .

5. Give an example to deduce
   

class Solution {
    
    public int maxSubArray(int[] nums) {
    
        int len = nums.length;
        int[] dp = new int[len];
        dp[0] = nums[0];

        int res = dp[0];
        for(int i = 1; i < len; i++){
    
            dp[i] = Math.max(nums[i], nums[i] + dp[i - 1]);
            if(dp[i] > res)res = dp[i];
        }

        return res;
    }
}

lt.392. Judging subsequences

[ Case needs ]

[ Train of thought analysis 1 , Direct brute force solution ]

Double pointer , Because it's to prove s Whether it is t String , So only in t The character of is equal to s The characters of , s The pointer in the string will move

Judge s Whether it is t The condition of the string becomes s Whether the pointer of has moved to s At the end of , Only in this way can it be explained s All characters in the string can
stay t Find the corresponding match in

[ Code implementation ]

class Solution {
    
    public boolean isSubsequence(String s, String t) {
    
        int len1 = s.length();
        int len2 = t.length();

        int i = 0, j = 0;
        
        while(i < len1 && j < len2){
    
            if(s.charAt(i) == t.charAt(j)){
    
                ++i;
            }
            ++j;
        }

        return i == len1;
    }
}

[ Train of thought analysis II , Dynamic programming ]

• This question should be regarded as an introduction to editing distance , Because from the meaning of the title, we can also find , You only need to calculate the deletion , No need to consider addition and replacement . Therefore, mastering this topic is also a foundation for the topic of editing distance to be explained later .

1. determine dp Array and subscript meaning

dp[i][j] Denotes the following i - 1 String ending with s, And the following j - 1 Bit terminated string t, The length of the same subsequence is dp[i][j].

Notice that this is judgment s Is it t The subsequence . namely t The length of is greater than or equal to s Of . Some students asked , Why should subscripts be expressed i-1 For the ending string , Why doesn't it mean subscript i For the ending string ？ use i It's OK to say ！ But I unify the following i-1 Calculate for the ending string , In this way, it will be easier to understand in the following recursive formula , If there is any doubt , You can keep looking down .

2. Determine the recurrence formula
   In determining the recurrence formula , First, consider the following two operations , It is arranged as follows ：

if (s[i - 1] == t[j - 1]) ⇒ t Found a character in s It also appears in
if (s[i - 1] != t[j - 1]) => amount to t To delete an element , Continue matching

• if (s[i - 1] == t[j - 1]), that dp[i][j] = dp[i - 1][j - 1] + 1, Because we found the same character , The length of the same subsequence should naturally be in dp[i-1][j-1] On the basis of 1（ If you don't understand , Look back dp[i][j] The definition of ）
• if (s[i - 1] != t[j - 1]), At this time, it is equivalent to t To delete an element ,t If the current element t[j - 1] Delete , that dp[i][j] And the value of that is see s[i - 1] And t[j - 2] The comparison results of , namely ：dp[i][j] = dp[i][j - 1];

3. dp Initialization of an array

As can be seen from the recurrence formula dp[i][j] All depend on dp[i - 1][j - 1] and dp[i][j - 1], therefore dp[0][0] and dp[i][0] It must be initialized .
Here you can already find , In defining dp[i][j] Why do you mean the following when you mean i-1 String ending with s, And the following j-1 String ending with t, The length of the same subsequence is dp[i][j].
Because this definition is in dp The initialization interval can be reserved in the two-dimensional matrix , Pictured ：

If defined dp[i][j] It's the following sign i String ending with s And the following j String ending with t, Initialization is more troublesome .

dp[i][0] Denotes the following i-1 String ending with , The same subsequence length as the empty string , So for 0. dp[0][j] Empathy .

In fact, here is only initialization dp[i][0] That's enough , But it is also convenient to initialize together , So we worked together , The code is as follows ：

4. Determine the traversal order

Similarly, we can see from the recursive formula that dp[i][j] All depend on dp[i - 1][j - 1] and dp[i][j - 1], Then the traversal order should also be from top to bottom , From left to right

5. Give an example to deduce dp Array
   

class Solution {
    
    public boolean isSubsequence(String s, String t) {
    
        int length1 = s.length(); int length2 = t.length();
        int[][] dp = new int[length1+1][length2+1];
        for(int i = 1; i <= length1; i++){
    
            for(int j = 1; j <= length2; j++){
    
                if(s.charAt(i-1) == t.charAt(j-1)){
    
                    dp[i][j] = dp[i-1][j-1] + 1;
                }else{
    
                    dp[i][j] = dp[i][j-1];
                }
            }
        }
        if(dp[length1][length2] == length1){
    
            return true;
        }else{
    
            return false;
        }
    }
}