package question;

/**
 * @author Roderland
 * @since 1.0
 */
public class Question132 {
 public static void main(String[] args) {
 System.out.println(new Question132().minCut("aab"));
 }

 public int minCut(String s) {
 int n = s.length();
 int[][] dp = new int[n][n];
 for (int k = 1; k < n; k++) {
 for (int i = 0; i + k < n; i++) {
 int j = i + k;
 if (!is(s.substring(i, j + 1))) {
 dp[i][j] = Integer.MAX_VALUE;
 for (int l = i; l < j; l++) {
 dp[i][j] = Math.min(dp[i][j], dp[i][l] + dp[l + 1][j] + 1);
 }
 }
 }
 }
 return dp[0][n - 1];
 }

 public boolean is(String s) {
 int i = 0;
 int j = s.length() - 1;
 while (i < j) {
 if (s.charAt(i++) != s.charAt(j--)) return false;
 }
 return true;
 }
}