This is the 23rd day of my participation in Gwen Challenge


If you are not familiar with dynamic programming, please refer to this chapter \color{red}{if you are not familiar with dynamic programming, please refer to this chapter ~}

Liver for many days – dynamic planning ten even – super delicate analysis | brush title punch card


This problem is very interesting, do not see regret! 😄 😄 😄 \color{green}{this question is very interesting, do not see regret! 😄 😄 😄 ~}

What problem can I choose to do dynamic programming?

Counting 1.

  • How many ways can I get to the bottom right corner
  • How many ways can I pick the sum of k numbers yes is sum

2. Find the maximum and minimum

  • The maximum numeric sum of the path from the upper left corner to the lower right corner
  • Maximum ascending subsequence length

3. Seek existence

  • Stone game, whether the first hand will win
  • Can we pick k numbers such that the sum is sum

Leecode 115. Different subsequences

Given a string s and a string t, count the number of occurrences of t in a subsequence of S.

A subsequence of strings is a new string formed by deleting some (or none) characters without interfering with the relative positions of the remaining characters.

(For example, “ACE” is a subsequence of “ABCDE”, but “AEC” is not)

The question data ensures that the answers fit into the range of 32-bit signed integers.

Example 1:

Enter: s = “rabbbit”, t = “rabbit”

Output: 3

Explanation: As shown below, there are three ways to get “rabbit” from S.

(Top arrow symbol ^ indicates the selected letter)

rabbbit

^ ^ ^ ^ ^ ^

rabbbit

^ ^ ^ ^ ^ ^

rabbbit

^ ^ ^ ^ ^ ^

Example 2:

Enter: s = “babgbag”, t = “bag”

Output: 5

Explanation: As shown below, there are five ways to get “bag” from S. (Top arrow symbol ^ indicates the selected letter)

babgbag

^ ^ ^

babgbag

^ ^ ^

babgbag

^ ^ ^

babgbag

^ ^ ^

babgbag

^ ^ ^Copy the code

Tip:

0 <= S. length, t.length <= 1000 s and T consist of letters

—

Four steps for dynamic planning ~~~ ❤️❤️❤️❤️

2.1. Dynamic planning component 1: State determination

To put it simply, when solving dynamic programming, you need to open an array. What does each element of the array f[I] or f[I][j] represent, similar to what x, y, and z represent in mathematical problems

The last step

If the s string is a subsequence of the T string, we directly compare whether the last letter is equal (because when both s and T have only one letter, they are the last letter)

For example: s = “babgbag”, t = “bag”

If the length of the s string is less than the length of the t string, it returns 0, no subsequence.

subproblems

Subproblem analysis, we determine if the last letter matches, so there are two cases

— If the last letter matches:

Can be deduced: dp [I] [j] = dp + 1] [I [j + 1) + dp [j], [I + 1] see j I + 1 + 1 is a subsequence, here with dp + 1] [I [j] because, for example: S =babc, t= BC, when the second b of the s string matches the first b of the T string, it needs to add the previously unmatched subsequence.

— If the last letter does not match:

It can be deduced that dp[I][j]=dp[I +1][j] to see if j is a subsequence of I +1, e.g. S = bac,t = BC

Nice \color{yellow}{very nice ~} very nice ❤️❤️❤️

2.2. Dynamic programming component 2: Transfer equation

We looked at the subproblem analysis, which is essentially the analysis of these two cases.

The transfer equation is easy to write:

dp[i][j]=dp[i+1][j+1]+dp[i+1][j]

dp[i][j]=dp[i+1][j]

2.3. Dynamic programming component 3: Initial conditions and boundary cases

The string length of s >= the string length of t

If t is empty, then empty can be a subsequence of S.

2.4. Dynamic programming component 4: Order of calculation

Top down or bottom up

Reference code

The language version

func numDistinct(s, t string) int {
        m, n := len(s), len(t)
        if m < n {
            return 0
        }
        dp := make([] []int, m+1)
        for i := range dp {
            dp[i] = make([]int, n+1)
            dp[i][n] = 1   // // For t, if t is null, null is a subsequence of the S string, so null is a subsequence group of each character of S
        }
        for i := m - 1; i >= 0; i-- {
            for j := n - 1; j >= 0; j-- {
                if s[i] == t[j] {
                    dp[i][j] = dp[i+1][j+1] + dp[i+1][j]
                } else {
                    dp[i][j] = dp[i+1][j]
                }
            }
        }
        return dp[0] [0]}Copy the code

JAVA version

 
    public int numDistinct(String s, String t) {
        int m = s.length(), n = t.length();
        if (m < n) {
            return 0;
        }
        int[][] dp = new int[m + 1][n + 1];
        for (int i = 0; i <= m; i++) {
            dp[i][n] = 1; // For t, if t is null, null is a subsequence of the s string, so null is a subsequence combination of each character of S.
        }
        for (int i = m - 1; i >= 0; i--) {
            char sChar = s.charAt(i);
            for (int j = n - 1; j >= 0; j--) {
                char tChar = t.charAt(j);
                if (sChar == tChar) {
                    dp[i][j] = dp[i + 1][j + 1] + dp[i + 1][j];
                } else {
                    dp[i][j] = dp[i + 1][j]; }}}return dp[0] [0];
    }

    @Test
    public void isnumDistinct(a) {
        int i = numDistinct("babc"."bc");
        Assert.assertNotNull(i);
    }


    

Copy the code

❤ ️ ❤ ️ ❤ ️ ❤ ️

Thank you very much talent can see here, if this article is written well, feel that there is something to ask for praise 👍 for attention ❤️ for share 👥 for handsome Oba I really very useful!!

If there are any mistakes in this blog, please comment, thank you very much!

At the end of this article, I recently compiled an interview material “Java Interview Process Manual”, covering Java core technology, JVM, Java concurrency, SSM, microservices, databases, data structures and so on. How to obtain: GitHub github.com/Tingyu-Note… , more attention to the public number: Ting rain notes, one after another.