給你一個(gè)字符串 s，請(qǐng)你將 s 分割成一些子串，使每個(gè)子串都是回文。
返回符合要求的 最少分割次數(shù) 。

解題思路：兩次dp

1、回溯

這道題拿到之后，分割子串，我立馬想到了回溯暴力去做。
基本思想：每次拿到分割后的子串去判斷一下它是否是回文，如果是則繼續(xù)分割，直到分割下標(biāo)達(dá)到s.length()；否則跳出進(jìn)行下一個(gè)分割點(diǎn)。

(1) 回溯（不帶記憶法），并且遞歸定義為：s[l:r]子串中擁有的最少回文串?dāng)?shù)量【超時(shí)】
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;
        // 確定子串的最后一個(gè)字符，開始為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記錄算出來的次數(shù)【超時(shí)】
● 第二次嘗試：用布爾二維dp數(shù)組，即dp[i][j]表示s[i:j]是否是回文串【超時(shí)】

用回溯，即使是帶有記憶法的回溯，在力扣中均超時(shí)。
所以說，這道題只能用dp去做，還是比較難的。

2、動(dòng)態(tài)規(guī)劃

(1) 定義dp數(shù)組
dp[i]：s[0:i]子串中 滿足題意的 最少分割次數(shù)

(2) 狀態(tài)轉(zhuǎn)移方程
假定現(xiàn)在計(jì)算dp[i]：
● 如果s[0:i]是一個(gè)回文串：dp[i] = 0
?理解：不用分割，所以是0.
● 如果s[0:i]不是一個(gè)回文串：
?● 遍歷分割點(diǎn) j（i-1 → 0），如果s[j+1, i]是回文串：分割次數(shù) cutCount = dp[j] + 1
?● 取最小的分割次數(shù)為dp[i]
?理解：至少要分割一次，這個(gè)分割點(diǎn)就是 j（s[0:j]、s[j+1, i]）

? ——如何判斷是否是回文串？
這個(gè)就是我們總是在做的事情了，即通過動(dòng)態(tài)規(guī)劃構(gòu)造二維布爾數(shù)組。
詳情見：【回文子串】647. 回文子串 - 簡(jiǎn)書 (jianshu.com)

(3) 初始化
無

(4) 遍歷順序
從左到右

(5) 舉例：略

class Solution {
    public int minCut(String s) {
        // 1. 構(gòu)造判斷是否回文的dp二維數(shù)組
        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. 構(gòu)造dp[i]：s[0:i]子串滿足題意的最少分割次數(shù)
        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īng)計(jì)算過的信息，后一部分也必須滿足回文
                // 遍歷j，如果s[j+1:i]是回文串，再計(jì)算切割次數(shù)
                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];
    }
}