Leetcode - 132. 分割回文串 II

class Solution {

    // 和上一题类似，先找到字符串s中所有是回文的子串，然后使用动态规划找到最少分割次数
    public int minCut(String s) {
        int length = s.length();
        char[] arr = s.toCharArray();
        if (length <= 1) {
            return 0;
        }

        // dp[l][r]表示字符串s的[l, r]区间上的子串是否为回文
        // 注意dp[l][r]的动态转移方程中包含dp[l + 1][r - 1]
        // 因此需要保证在判断dp[l][r]时dp[l + 1][r - 1]已经被置为正确的值
        boolean[][] dp = new boolean[length][length];
 
        for (int r = 0; r < length; r++) {
             
            // 长度为1的字符串一定是回文
            dp[r][r] = true;
             
            for (int l = r - 1; l >= 0; l--) {
 
                // 如果l和r指向的字符不同，则当前子串肯定不是回文
                // 如果l和r指向的字符相同，则r - l <= 2时当前子串是回文
                // 如果l和r指向的字符相同，且r - l > 2，那么dp[l][r]取决于dp[l + 1][r - 1]
                dp[l][r] = arr[l] != arr[r] ? false : (r - l <= 2 ? true : dp[l + 1][r - 1]);
            }
        }

        // times[i]表示s的前i个字符组成的子串的最小分割次数
        int[] times = new int[length];

        // 前i个字符组成的子串最多分割i次，因此先将times各个元素初始化为最大的能取到的值
        for (int i = 0; i < length; i++) {
            times[i] = i;
        }

        // times[0]肯定是0，不用管，因此从下标1开始计算times的各个元素
        for (int i = 1; i < length; i++) {
            
            // 如果前i个字符本身可以组成回文，则times[i]为0
            if (dp[0][i]) {
                times[i] = 0;
                continue;
            }

            // 如果前i个字符不能组成回文
            // 那么可以尝试在[1, i]区间上找到一个下标j，使得s的[j, i]部分是回文
            // 那么显然，要将前i个字符都切分成回文，总共需要times[j - 1] + 1次
            for (int j = 1; j <= i; j++) {
                if (dp[j][i]) {
                    times[i] = Math.min(times[i], times[j - 1] + 1);
                }
            }
        }
        return times[length - 1];
    }
}