132.txt

class Solution {
    int dp[];
    public int minCut(String s) {
        dp=new int[s.length()];
        Arrays.fill(dp,-1);
        int res= dfs(s,0);

        return res;
    }
    
    public int dfs(String s,int l){
        if(l>=s.length())return 0;
        if(check(s,l,s.length()-1))return 0;
        if(dp[l]!=-1)return dp[l];
        int res=Integer.MAX_VALUE;
        for(int i=l;i<s.length();i++){
            if(check(s,l,i)){
                res=Math.min(res,1+dfs(s,i+1));
            }
        }
        dp[l]=res;
        return res;
    }
    
    public boolean check(String s,int l,int r){
        while(l<r){
            if(s.charAt(l++)!=s.charAt(r--))return false;
        }
        return true;
    }
}