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