This is the 7th day of my participation in the November Gwen Challenge. Check out the details: The last Gwen Challenge 2021

After talking about the theory of dynamic programming in the last article, this time we are going to practice a wave of speakers, and today we are going to do some classic subsequence problems. This kind of problem gives me the feeling that state and choice are not easy to say, not so clear, let’s mainly learn the definition of DP array (routine 🤤).

Longest Increasing Subsequence (LIS)

The description of question 300 is as follows:

Given an integer array nums, find the length of the longest strictly increasing subsequence. Where a subsequence is a sequence derived from an array that deletes (or does not delete) the elements in the array without changing the order of the remaining elements. For example, [3,6,2,7] is a subsequence of the array [0,3,1,6,2,2,7].

I started out with a little bit of dynamic programming, and the first time I did this problem, I defined dp arrays like this:

Dp [I] represents the length of the longest increasing subsequence from nums[0] to NUMs [I]. Sure enough, I was too young to think that as long as I figured out dp[n-1], I could get the answer. But I can’t figure out the state transition equation, so let’s quit.

Don’t go, don’t go, when we define the dp array as:

Dp [I] represents the length of the longest increasing subsequence ending in NUMs [I]. So when we come to nums[I], because it is an increasing subsequence, we just need to find the previous sequence ending with a smaller element than nums[I], and join nums[I] to form a new increasing subsequence, and the length of the new subsequence is increased by 1. Choose the longest of these as the value of dp[I]. The base case is the longest increasing subsequence ending in nums[I] including at least itself, so length 1. Based on the above analysis, we can also write the state transition equation

dp[i]=Math.max(dp[i],dp[j]+1);/ / the nums [j] < nums [I]
Copy the code

Direct on a wave of code (family, running force buckle knocked a wave, a pass, bengbu live 😭)

var lengthOfLIS = function(nums) {
    let dp=Array(nums.length).fill(1);
    for(let i=0; i<nums.length; i++){for(let j=0; j<i; j++){if(nums[j]<nums[i]){
                dp[i]=Math.max(dp[i],dp[j]+1); }}}let res=0;
    // Because of our dp array definition, finally we have to iterate through the dp array to find the one with the largest length
    for(let i=0; i<dp.length; i++){ res=Math.max(res,dp[i]);
    }
    return res;
};
Copy the code

Longest Common Subsequence (LCS)

OfferII 95 The topic description is as follows:

Given two strings text1 and text2, return the length of the longest common subsequence of the two strings. If no common subsequence exists, return 0.

This problem involves two strings, we should define a two-dimensional dp array:

Dp [I][j] represents the length of the longest common subsequence of text1[0… I] and Text2 [0…j]. Base case text1 or text2 is an empty string, which has no subsequence in common with any string, so it has length 0.

We can draw the following DP table:

So how do we derive our dp[I][J]? Text1 [I]=dp[i-1][j-1] =dp[i-1][j-1]+1; text1[I]=dp[I][j] +1; The state transition equation can be written as follows:

dp[i][j]=dp[i-1][j-1] +1//text1[i]==text2[j]
dp[i][j]=Math.max(dp[i-1][j],dp[i][j-1])//text1[i]! ==text2[j]
Copy the code

Translated into code as follows:

var longestCommonSubsequence = function(text1, text2) {
    let m=text1.length;
    let n=text2.length;
    // Initializes a wave array
    let dp=Array(m+1);
    for(let i=0; i<=m; i++){ dp[i]=Array(n+1).fill(0);
    } 
    for(let i=1; i<=m; i++){for(let j=1; j<=n; j++){Text1 has the ith character index i-1 and text2 has the JTH character index j-1.
            if(text1[i-1]==text2[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];
};
Copy the code

Longest sequence of rhymes

The description of question 516 is as follows:

Given a string s, find the longest sequence of subroutines and return the length of that sequence.

Although this is still a string problem, if we define the DP array as one-dimensional, such as “dp[I] represents the length of the longest sequence of degenerate subrons ending in nums[I]”, we will find that the state transition equation is nowhere to start. That’s when you can think about ascending dimensions. We define the dp array as follows:

Dp [I][j] represents the length of the longest loop sequence in the substring s[I…j]. Base case is a single character. The longest loop sequence is itself, so it is 1. So how do we derive our dp[I][j]? If s[I] and s[j] are equal, dp[I][j]=dp[I +1][j-1]+2(adding s[I] and s[j] to the subroutine sequence). If not, we can see which case is the longest. The length is the value of dp[I][j]. Namely, the equation of state is as follows:

dp[i][j]=dp[i+1][j-1] +2//s[i]==s[j]
dp[i][j]=Math.max(dp[i+1][j],dp[i][j-1])//s[i]! ==s[j]
Copy the code

This state transition equation dictates that we need to iterate backwards through the DP array because we need either dp[I +1][j-1] or dp[I +1][j] to compute dp[I][j].

The code is as follows:

var longestPalindromeSubseq = function(s) {
     let str0=s.split(' ');
     let dp=Array(str0.length);
    for(let i=0; i<str0.length; i++){ dp[i]=Array(str0.length).fill(0);
    }
     for(let i=0; i<str0.length; i++){ dp[i][i]=1;
     }
     for(let i=str0.length-2; i>=0; i--){for(let j=i+1; j<str0.length; j++){if(str0[i]==str0[j]){
                 dp[i][j]=dp[i+1][j-1] +2;
             }else{
                 dp[i][j]=Math.max(dp[i+1][j],dp[i][j-1]); }}}return dp[0][str0.length-1];
};
Copy the code

Initialize an array (); initialize an array ();

// The first initialization method, bingo
let dp1=Array(5);
    //console.log(dp[1][1]);
    for(let i=0; i<5; i++){ dp1[i]=Array(5).fill(0);
    }
console.log(dp1);
dp1[1] [1] =1;
console.log(dp1);
// The second initialization method, which I wrote wrong at the beginning, was lazy, but did not expect to step on the detail pit.
let dp2=Array(5).fill(Array(5).fill(0));
console.log(dp2);
dp2[1] [1] =1;
console.log(dp2);
Copy the code

See the error 😅

We have learned a few seed sequences dp array definition routine, you learn fei? And you’ll notice that when we define the DP array, find the base case, and derive the state transition equation, it’s pretty quick to write code, sometimes you have to scratch the edges.