import java.util.*;
public class Solution {
    //判斷是否為回文串
    public boolean func(String s,int start,int end) {
        while(start<end) {
            if(s.charAt(start)!=s.charAt(end)) {
                return false;
            }
            start++;
            end--;
        }
        return true;
    }
    public int minCut (String s) {
        int len = s.length();//字符串的長度
        if(len == 0) return 0;//當長度為0時直接返回0
        int[] count = new int[len + 1];//用于記錄狀態(tài)
        //狀態(tài)初始化
        for(int i = 0;i <= len;i ++) {
            count[i] = i-1;
        }
        for(int i = 1;i <= len;i++) {
            for(int j = 0;j <= i-1;j++) {
                if(func(s,j,i-1)) {
                    count[i] = Math.min(count[i],count[j]+1);//狀態(tài)轉移方程
                }
            }
        }
        return count[len];//返回結果
    }
}

import java.util.*;
public class Solution {
    //判斷是否為回文串
    public boolean[][] func2 (String s) {
        int len = s.length();//字符串的長度
        boolean[][] ret = new boolean[len][len];
        //記錄狀態(tài)的二維數(shù)組，默認值為false
        //由于i<=j<len,所以ret數(shù)組實際只更新了一半
        for(int i = len;i >= 0;i--) {
            for(int j = i;j<len;j++) {
                if(i == j) {
                    ret[i][j] = true; //單字符比為回文串
                }else if(j == i+1) {
                    if(s.charAt(i) == s.charAt(j)) {
                        ret[i][j] = true; //相鄰字符相同為回文串
                    }else{
                        ret[i][j] = false;//相鄰字符不同就不是回文串
                    }
                }else{
                    ret[i][j] = (s.charAt(i) == s.charAt(j)) && ret[i+1][j-1];
                    //其余轉移情況
                }
            }
        }
        return ret;//返回結果
    }
    public int minCut (String s) {
        int len = s.length();
        if(len == 0) return 0;
        int[] count = new int[len + 1];
        //狀態(tài)初始化
        for(int i = 0;i <= len;i ++) {
            count[i] = i-1;
        }
        boolean[][] ret = func2(s);//調用判斷回文串方法，獲得所有字符子串的是否為回文串的情況
        for(int i = 1;i <= len;i++) {
            for(int j = 0;j <= i-1;j++) {
                //直接在ret數(shù)組中找結果，避免反復調用回文串判斷方法
                if(ret[j][i-1]) {
                    count[i] = Math.min(count[i],count[j]+1);//狀態(tài)轉移方程
                }
            }
        }
        return count[len];//返回結果
    }
}

import java.util.*;
public class Solution {
    public int minCut(String s) {
        int len = s.length();//字符串的長度
        if(len == 0) return 0;
        int []count = new int[len+1]; //存放最小分割次數(shù)狀態(tài)的數(shù)組
        boolean [][]p = new boolean[len][len];//存放[i,j]字符區(qū)間是否為回文串的二維數(shù)組
        for(int i = 0; i <= len; i++) count[i] = len - i - 1;//狀態(tài)初始化
        for(int i = len-1;i >= 0;i--){
            for(int j = i;j < len;j++){
                //j-i<2 條件成立且第一個條件成立包含著單個字符串和相鄰字符串的情況
                //p[i+1][j-1] 為 ture 且第一個條件成立則代表著其他的回文串狀態(tài)轉移類型
                //以上情況有一項成立則F（i，j）為 ture
                if(s.charAt(i) == s.charAt(j) && (j-i<2||p[i+1][j-1])){
                    p[i][j] = true;
                    count[i] = Math.min(count[i],count[j+1]+1);//狀態(tài)轉移方程
                }
            }
        }
        return count[0];//返回結果
    }
}

import java.util.*;
public class Solution {
    public int minCut(String s) {
        int len = s.length();//字符串的長度
        if(len == 0) return 0;
        int[] count = new int[len + 1];
        for(int i = 0; i <= len; i++) count[i] = i - 1;//狀態(tài)初始化
        for(int i = 0; i < len; i++) {
            func3(s, i, i, count);//奇數(shù)個字符的回文串
            func3(s, i, i + 1, count);//偶數(shù)個字符的回文串
        }
        return count[len];//返回結果
    }     
    private  void func3(String s, int i, int j, int[] count) {
        //不超過字符串s的區(qū)間范圍且下標i的字符和下標j的字符相等的條件下向兩頭擴展，得到最長的回文串，以此來求出狀態(tài)
        while(i >= 0 && j < s.length() && s.charAt(i) == s.charAt(j)) {
            count[j + 1] = Math.min(count[j + 1], count[i] + 1); //狀態(tài)轉移
            --i;//左區(qū)間擴展一格
            ++j;//右區(qū)間擴展一格
        }
        return;
    }  
}