public int minCut(String s) {
		if (s == null || s.isEmpty())
			return 0;

		int[] mincut=new int[s.length()+1];
		for(int i=0;i<mincut.length;i++){			
			mincut[i]=i;
		}
		boolean[] ispalin=new boolean[s.length()];
		
		for(int i=1;i<=s.length();i++){
			for(int k=0;k<i;k++){
				ispalin[k]=false;
				if (s.charAt(k)==s.charAt(i-1) && (k+1>=i-1 || ispalin[k+1])) {
					ispalin[k]=true;
					mincut[i]=Math.min(mincut[i],mincut[k]+1);
				}
			}
		}
		
		return mincut[s.length()]-1;
	}