I. Topic Description:

Ii. Thinking analysis:

This article is mainly a supplement to the general idea of dynamic programming mentioned in the previous article, because sometimes it seems that the state transition equation is particularly difficult to write. In many cases, it is clearly known that this is dynamic programming, but the state transition equation cannot be written.

This article focuses on the second step: determining the state

We’re going to talk about determining the state and we’re going to expand that into state representation and state computation

State said

The state representation is what the state is, that is, dp[I][j] represents the sum of the maximum/minimum/satisfying conditions I and j.

In this case, dp[I][j] is the maximum length of a subsequence of I lengths before string 1 and j lengths before string 2.

State calculation

State calculation is to figure out step by step how to get dp[I][j], you can certainly in the process of papyrus calculation, bold assumptions, and finally cut down to the answer

If you’re confused about how to get this expression, you can change it to which of the previous subquestions you got it from, or the answer is made up of several possibilities.

In this problem, we think of dp [I] [j], affirmation and dp [j], [I – 1] dp [1], [I] dp [I – 1] [1], and for the STR [I] and STR [j] is nothing but only STR [I] = = STR [j], STR [I]! = STR [j] two possibilities.

It seems like the two possibilities are easier to analyze,

  • str[i] == str[j]Dp [I][j] = dp[I – 1][j – 1] + 1
  • str[i] ! = str[j], dp[i-1][j-1] is also considered by DP [i-1][J], so dp[i-1][j-1] is no longer included in the calculation. whenstr[i] ! = str[j], the longest subsequence is left with str1[I] or str2[j] (neither of which has just been ruled out)

    • In this case, dp[I][j] == dp[I][j-1], so we can use dp[I][j-1] as a possibility of dp[I][j]

Then the state transition equation is drawn:

dp[i][j] = max(dp[i - 1][j], dp[i][j - 1]);
if(str1[i] == str2[j]) dp[i][j] = max(dp[i][j], dp[i - 1][j - 1] + 1);
Copy the code

Iii. AC code:

class Solution {
public:
    int longestCommonSubsequence(string text1, string text2) {
        int m = text1.size(a);int n = text2.size(a);int dp[m + 1][n + 1];
        dp[0] [0] =0, dp[0] [1] =0, dp[1] [0] = 0;
        for(int i = 0; i <= m; i ++){
            for(int j = 0; j <= n; j ++){
                if(i == 0 || j == 0){
                    dp[i][j] = 0;
                    continue;
                }
                dp[i][j] = 0;
                dp[i][j] = max(dp[i][j - 1], dp[i - 1][j]);
                // printf("%d ", dp[i][j]);
                if(text1[i - 1] == text2[j - 1])dp[i][j] = max(dp[i][j], dp[i - 1][j - 1] + 1);
                // printf("%d \n ", dp[i][j]);}}returndp[m][n]; }};Copy the code

Iv. Summary:

This article will define the state more detailed, I personally think it is helpful to learn dynamic programming, but after all, I do not know whether it is really helpful, brothers can communicate in the comment area.

This article is participating in the “Nuggets 2021 Spring Recruiting activity”, click to see the details of the activity