题目链接

132. 分割回文串 II

思路

分析动态规划题目的时候只需要考虑最后一个阶段，因为所有的阶段转化都是相同的，考虑最后一个阶段容易发现规律

在数组的动态规划问题中，一般 dp[i] 都是表示以 nums[i] 为结尾的状态；dp[i][j] 分别表示 以 nums1[i] 和 nums2[j] 为结尾的状态，以此类推

字符串也是个数组，是字符数组

表示状态

首先构思一下我们需要存储的信息，以此来确定 dp 数组的维数：

找状态转移方程

边界处理

代码

dp数组版

class Solution {
    public int minCut(String s) {
        int n = s.length();
        if(n < 2){
            return 0;
        }
        // dp[i]表示 s[0 : i] 符合要求的最少分割次数
        // dp[i] = min(dp[j] + 1 if s[j + 1: i] 是回文 for j in range(i))
        int[] dp = new int[n + 3];
        // 表示 s[i:j] 是否是回文串
        boolean[][] checkPalindrome = getCheckPalindromeArray(s.toCharArray());

        // 最坏情况下是每个字符单独成串,所以需要每个字符都切割,即需要切 n - 1 下
        for(int i = 0; i < n; i++){
            dp[i] = i;
        }

        // 1 个字符的时候，不用判断，因此 i 从 1 开始
        for(int i = 1; i < n; i++){
            // 如果 s[0 : i] 是回文串,那么就不用切割
            if(checkPalindrome[0][i]){
                dp[i] = 0;
                continue;
            }

            // 如果不是回文串,那么需要判断怎么切割 s[0 : i]
            for(int j = 0; j < i; j++){
                // dp[j], 即 s[0 : j] 的切割次数已经计算好了,现在只需要判断 s[j + 1 : i] 是不是回文串
                // 如果是回文串,那么 dp[i] = min(dp[i], dp[j] + 1)
                if(checkPalindrome[j + 1][i]){
                    dp[i] = Math.min(dp[i], dp[j] + 1);
                }
            }
        }

        return dp[n - 1];
    }

    public boolean[][] getCheckPalindromeArray(char[] s) {
        boolean[][] checkPalindrome = new boolean[s.length][s.length];

        for(int i = 0; i < s.length; i++){
            checkPalindrome[i][i] = true;
        }
        // 枚举每一个子串
        for(int j = 1; j < s.length; j++){
            for(int i = 0; i < j; i++){
                // 如果一个串的左右两个字符相同,且中间的子串是回文串,那么这个串就是回文串
                checkPalindrome[i][j] = (
                        (s[i] == s[j]) && ((j - i <= 2) || checkPalindrome[i + 1][j - 1])
                );
            }
        }

        return checkPalindrome;
    }
}