132. 分割回文串Ⅱ

题目来源

132. 分割回文串 II

思路

方法一

动态规划

class Solution {
    public int minCut(String s) {
        int len = s.length();
        char[] cs = s.toCharArray();

        // 预处理是不是回文串，是的话就为true
        boolean[][] st = new boolean[len][len];

        // 为了确保可以计算到st[i+1][j-1]，j要从小增加到大，i要从j一直变小
        for(int j = 0;j<len;j++){
            for(int i = j;i>=0;i--){
                // 长度为1一定是一个回文串
                if(i == j){
                    st[i][j] = true;
                }else if(j-i+1 == 2){
                    // 如果长度为2，要保证两个字母相同
                    if(cs[i] == cs[j]){
                        st[i][j] = true;
                    }
                }else {
                    // 除了要保证第i个和第j个是同样的字母外，还要保证去掉第一个和最后一个字母后依旧是回文串
                    if(cs[i] == cs[j] && st[i+1][j-1] == true){
                        st[i][j] = true;
                    }
                }
            }
        }

        int[] f = new int[len];
        for(int j = 1;j<len;j++){
            // 如果0到j是回文串，那么分割次数为0
            if(st[0][j]){
                f[j] = 0;
            }else{
                // 有两种分割方式，一种是将第j个字母作为一个单独的回文串分割
                f[j] = f[j-1]+1;

                // 第二种是之前的所有字母中和当前的第j个字母 组合成的子串 是否构成回文串，然后在所有情况下取最小值
                for(int i = 1;i<len;i++){
                    if(st[i][j]){
                        f[j] = Math.min(f[j], f[i-1]+1);
                    }
                }
            }
        }
        return f[len-1];
    }
}

参考来源

1. 宫水三叶

【题解】力扣132. 分割回文串Ⅱ

原文：https://www.cnblogs.com/zzzzzy2k/p/14749415.html