public int minCut(String s) {
		if(s==null || s.length()==0){
			return 0;
		}
		
		int len=s.length();
		boolean[][] dp=new boolean[len][len];
		int[] res=new int[len+1];
		
		for (int i = 0; i < len; i++) {
			res[i]=len-1-i;
		}
		
		for(int i=len-2;i>=0;i--){
			for(int j=i;j<len;j++){
				if(s.charAt(i)==s.charAt(j) && (j-i<3 || dp[i+1][j-1])){
					dp[i][j]=true;
					if(j==len-1){
						res[i]=0;
					}else{
						res[i]=Math.min(res[i], 1+res[j+1]);
					}
				}
			}
		}
		
		return res[0];
    }