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 132. Split palindrome string II

Given a string s, please split s into substrings so that each substring is palindrome.

Returns the minimum number of splits that meet the requirement.

Example 1:

Enter: s = “aab”

Output: 1.

Explanation: it takes only one split to split S into [“aa”,”b”].

Example 2:

Input: s = “a”

Output: 0

Example 3:

Input: s = “ab”

Output: 1.

Tip:

1 <= s.length <= 2000

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. direct

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 palindrome string verification, and the second step 😄😄😄 \color{green}{of course, this is only a palindrome for characters I through j, and the second step 😄 😄 😄 ~}

Similarly, if f[0][I] = true (palindrome), it does not need to be divided. Otherwise, it does need to be divided. We use I to traverse each j

If it is a palindrome, we record min{f[I],f[j]+1}

For example string: “CDD “, minimum 1 times, when using the second letter D to traverse c, D, D three characters, in traversing the first d is palindrome f[1][2] needs f[2] = 0+1 times, traversing the second d is f[2][2],f[j]+1 = 2 times, so, it will get min{f[I],f[j]+1}

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)}}}}int[] f = new int[n];
        Arrays.fill(f, Integer.MAX_VALUE);
        for (int i = 0; i < n; ++i) {
            if (g[0][i]) {
                f[i] = 0;
            } else {
                for (int j = 0; j < i; ++j) {
                    if (g[j + 1][i]) {  // The reason for j+ 1 is that, instead of starting at 0, we already know f[0][I]
                        f[i] = Math.min(f[i], f[j] + 1);  // Please refer to the above instructions.}}}}return f[n - 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! ❤ ️ ❤ ️ ❤ ️ ❤ ️