力扣 剑指 Offer II 094. 最少回文分割

题目来源：https://leetcode.cn/problems/omKAoA/

大致题意：
给一个字符串，将字符串分割成子串，其中每个子串都是回文串，求所需要的最小分割次数

思路

对于字符串 s[0, j] 范围的子串，若 s[i, j] 是回文串，那么 s[0, j] 的最少回文分割次数即为 s[0, i - 1] 的最少回文分割次数 +1

于是可以得到状态转移方程：

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

具体实现时，可以先处理一个布尔数组 f[n][n]，用来表示s[i, j] 是不是回文串

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

代码：

public int minCut(String s) {
    
        int n = s.length();
        // 用来表示 s[i, j] 是否是回文串的标志数组
        boolean[][] f = new boolean[n][n];
        // 初始化都为 true， 主要是将 i >= j 时的数组元素处理为 true
        for (int i = 0; i < n; i++) {
    
            Arrays.fill(f[i], true);
        }
        // 动态规划，完成标志数组
        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);
            }
        }
        // 存最少回文分割次数
        int[] dp = new int[n];
        // 初始化都为最大值
        Arrays.fill(dp, n);
        // 动态规划
        for (int i = 0; i < n; i++) {
    
            // 如果子串 s[0, i] 是回文串，那么分割次数为 0
            if (f[0][i]) {
    
                dp[i] = 0;
                continue;
            }
            for (int j = 0; j < i; j++) {
    
                // 当子串为回文串时，更新最小分割次数
                if (f[j + 1][i]) {
    
                    // 状态转移方程
                    dp[i] = Math.min(dp[j] + 1, dp[i]);
                }
            }
        }
        return dp[n - 1];
    }