This article is participating in the “Java Theme Month – Java brush questions clock”, see < activity links > for more details.

【Java brush questions punch card 】 Brushing questions is much better than playing games, and the sense of achievement is getting stronger and stronger. I insist on brushing several questions every day, exercising for 30 minutes every day, waiting for 8-block abs and waiting for offers from big factories.

Then do it! This column is all about dynamic planning, I will start from the shallow to the deep, step by step, brush questions is such a need for continuous memory – Ebbinghaus memory method 2121112. There isn’t much about dynamic programming, but it’s a must for every programmer


This is a classic 😄😄😄 \color{green}{😄 😄 😄 ~}

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 131. Split palindrome strings

Given a string s, please split s into substrings so that each substring is a palindrome string. Returns all possible segmentation schemes for S.

A palindrome string is a string that is read forward and backward identically.

Example 1:

Enter: s = “aab”

Output: [[” a “, “a”, “b”], [” aa “, “b”]]

Example 2:

Input: s = “a”

Output: [[” a “]]

Tip:

1 <= s.length <= 16

The “S” is a lowercase letter only

—

~~~ ❤️❤️❤️❤️

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

We can figure out all the possible strings of characters the same way we did before.

Let’s use the following example to illustrate. The following figure shows the judgment process of the first and second steps. Obviously, the last step is the letter B with subscript 4 compared with all the previous elements to get the longest substring of the text.

subproblems

We can see that if f[I] =f[j], to determine that it’s a palindrome string, we need to determine

F [I]j] = f[I +1]f[j-1] : from I to j is a palindrome string, then from I +1 to j-1 must also be a palindrome string

So this is the figure above and we need to know that a is equal to a

1.2. Dynamic programming component 2: Transfer equation

For a string length from I to j, consider it a palindrome string:

f[i]j] = f[i+1]f[j-1]

We also know that f[I +1][j-1] is a given, because the result of the last step has been saved, that is f[I +1][j-1] = f[I +2]f[j-2]

1.3. Dynamic programming component 3: initial conditions and boundary cases

When the number of remaining decision letters <3 and f[I] = f[j], it must be a palindrome string.

For the letter itself f[I][I], the string from I to I, it’s also a palindrome.

1.4. Dynamic programming component 4: Order of calculation

As shown above, we use j to match 0 to I (I < j).


Of course, this is only for characters i to j Is the palindrome string validation, and the second step is to recursively find all the characters that might be palindromes and add them to the array. 😄 😄 😄 \color{green}{of course, this is just to verify that the characters from I to j are palindromes. The second step is to recursively find all possible palindromes and add them to the array. 😄 😄 😄 ~}

If the string is “ABA “, we know that there are two cases: A,a,a and ABA

Just a little bit about recursion, okay

  1. Each recursion boundary is the length of the character, the split character is added to the number of result sets, and the end of the recursion.

  2. Judge whether it is palindrome, because it is palindrome to conform to the meaning of the topic

  3. When I = 0, j = 0 and 1 recursively add to the split array

  4. This is just an array of temporary results to be removed when used.

Reference code

Java version

class Solution {
    boolean[][] dp;
    List<List<String>> ret = new ArrayList<List<String>>();
    List<String> ans = new ArrayList<String>();
    int n;

    public List<List<String>> partition(String s) {
        n = s.length();
        dp = new boolean[n][n];
       char[] charArray = s.toCharArray();
        for (int i = 0; i < n; i++) {
            dp[i][i] = true; // Palindrome to itself
        }
        for (int j = 1; j < n; j++) {
            for (int i = 0; i < j; i++) {
                if(charArray[i] ! = charArray[j]) { dp[i][j] =false;
                } else {
                    if (j - i < 3) {
                        dp[i][j] = true;
                    } else {
                        dp[i][j] = dp[i + 1][j - 1]; // If (j - I > 3) {// If (j - I > 3)
                    }
                }
            }
        }
         dfs(s, 0);
            return ret;
    }

    public void dfs(String s, int i) {
        if (i == n) {
            ret.add(new ArrayList<String>(ans));
            return;
        }
        for (int j = i; j < n; ++j) {
            if (dp[i][j]) {
                ans.add(s.substring(i, j + 1));
                dfs(s, j + 1);
                ans.remove(ans.size() - 1); }}}}Copy the code

Thank you for reading this, if this article is well written and if you feel there is something to it

Ask for a thumbs up 👍 ask for attention ❤️ ask for share 👥 for 8 abs I really very useful!!

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