【回文序列】132. 分割回文串II

给你一个字符串 s，请你将 s 分割成一些子串，使每个子串都是回文。
返回符合要求的 最少分割次数 。

解题思路：两次dp

1、回溯

这道题拿到之后，分割子串，我立马想到了回溯暴力去做。
基本思想：每次拿到分割后的子串去判断一下它是否是回文，如果是则继续分割，直到分割下标达到s.length()；否则跳出进行下一个分割点。

(1) 回溯（不带记忆法），并且递归定义为：s[l:r]子串中拥有的最少回文串数量【超时】
class Solution {
    public int minCut(String s) {
        if(isMeet(s, 0, s.length()-1)) return 0; 
        return recur(s, 0, s.length() - 1)-1;
    }
    public int recur(String s, int l, int r){
        if(l > r) return 0;
        else if(l == r) return 1;
        int minCut = Integer.MAX_VALUE;
        // 确定子串的最后一个字符，开始为l
        for(int i=l; i<=r; i++){
            int curCut = 1;
            if(isMeet(s, l, i)){
                curCut += recur(s, i+1, r);
                if(curCut < minCut) minCut = curCut;
            }
        }
        return minCut;
    }
    public boolean isMeet(String s, int l, int r){ // s[l:r] != ""
        while(l < r){
            if(s.charAt(l) != s.charAt(r)) return false;
            l++;
            r--;
        }
        return true;
    }
}

(2) 回溯（基于上述算法，新增记忆法）
● 第一次尝试：用HashMap记录算出来的次数【超时】
● 第二次尝试：用布尔二维dp数组，即dp[i][j]表示s[i:j]是否是回文串【超时】

用回溯，即使是带有记忆法的回溯，在力扣中均超时。
所以说，这道题只能用dp去做，还是比较难的。

2、动态规划

(1) 定义dp数组
dp[i]：s[0:i]子串中 满足题意的 最少分割次数

(2) 状态转移方程
假定现在计算dp[i]：
● 如果s[0:i]是一个回文串：dp[i] = 0
 理解：不用分割，所以是0.
● 如果s[0:i]不是一个回文串：
 ● 遍历分割点 j（i-1 → 0），如果s[j+1, i]是回文串：分割次数 cutCount = dp[j] + 1
 ● 取最小的分割次数为dp[i]
 理解：至少要分割一次，这个分割点就是 j（s[0:j]、s[j+1, i]）

⭕ ——如何判断是否是回文串？
这个就是我们总是在做的事情了，即通过动态规划构造二维布尔数组。
详情见：【回文子串】647. 回文子串 - 简书 (jianshu.com)

(3) 初始化
无

(4) 遍历顺序
从左到右

(5) 举例：略

class Solution {
    public int minCut(String s) {
        // 1. 构造判断是否回文的dp二维数组
        boolean[][] isMeet = new boolean[s.length()][s.length()];
        for(int i=s.length()-1; i>=0; i--){
            for(int j=i; j<s.length(); j++){
                if(i == j) isMeet[i][j] = true;
                else if(j - i == 1) isMeet[i][j] = (s.charAt(i) == s.charAt(j));
                else isMeet[i][j] = (s.charAt(i) == s.charAt(j) && isMeet[i+1][j-1]);
            }
        }
        // 2. 构造dp[i]：s[0:i]子串满足题意的最少分割次数
        int dp[] = new int[s.length()];
        for(int i=0; i<s.length(); i++){
            // 如果s[0:j]是回文串，那么不用切割
            if(isMeet[0][i]) dp[i] = 0;
            else{ // 必须切割，找切割最少的
                // 分成两部分思考：前一部分是利用dp已经计算过的信息，后一部分也必须满足回文
                // 遍历j，如果s[j+1:i]是回文串，再计算切割次数
                int minCount = Integer.MAX_VALUE;
                for(int j=i-1; j>=0; j--){
                    if(isMeet[j+1][i]) minCount = Math.min(minCount, dp[j] + 1);
                }
                dp[i] = minCount;
            }
        }
        return dp[s.length()-1];
    }
}