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