Offer II 094. Minimum palindrome segmentation

Title source ：https://leetcode.cn/problems/omKAoA/

General meaning ：
Give a string , Split the string into substrings , Each substring is a palindrome string , Find the minimum number of segmentation required

Ideas

For strings s[0, j] Substring of range , if s[i, j] It's a palindrome string , that s[0, j] The minimum number of palindrome segmentation is s[0, i - 1] Minimum palindrome segmentation times +1

So we can get the state transition equation ：

dp[j] = min(dp[i] + 1), 0 < i < j

Concrete implementation , You can deal with a Boolean array first f[n][n], Used to represent s[i, j] Is it a palindrome string

f[i][j] = (f[i + 1][j - 1] & s[i] = s[j])

Code ：

public int minCut(String s) {
    
        int n = s.length();
        //  Used to represent  s[i, j]  Whether it is the flag array of palindrome string 
        boolean[][] f = new boolean[n][n];
        //  Initialization is  true,  Mainly is to  i >= j  The array element of is processed as  true
        for (int i = 0; i < n; i++) {
    
            Arrays.fill(f[i], true);
        }
        //  Dynamic programming , Completion flag array 
        for (int i = n - 1; i >= 0; i--) {
    
            for (int j = i + 1; j < n; j++) {
    
                f[i][j] = f[i + 1][j - 1] && s.charAt(i) == s.charAt(j);
            }
        }
        //  Save the minimum palindrome segmentation times 
        int[] dp = new int[n];
        //  Initialization is the maximum 
        Arrays.fill(dp, n);
        //  Dynamic programming 
        for (int i = 0; i < n; i++) {
    
            //  If the substring  s[0, i]  It's a palindrome string , Then the number of divisions is  0
            if (f[0][i]) {
    
                dp[i] = 0;
                continue;
            }
            for (int j = 0; j < i; j++) {
    
                //  When the substring is a palindrome string , Update the minimum number of divisions 
                if (f[j + 1][i]) {
    
                    //  State transition equation 
                    dp[i] = Math.min(dp[j] + 1, dp[i]);
                }
            }
        }
        return dp[n - 1];
    }