1
class Solution {
2
  int dp[];
3

4
  public boolean pali(int i, int j, String s) {
5

6
    // int j=s.length()-1,i=0;
7
    while (i <= j) {
8
      if (s.charAt(i) != s.charAt(j)) return false;
9
      i++;
10
      j--;
11
    }
12

13
    return true;
14
  }
15

16
  public int cut(String s, int i, int n, int dp[]) {
17
    if (i == n) return 0;
18
    if (dp[i] != -1) return dp[i];
19

20
    int min = Integer.MAX_VALUE;
21
    for (int j = i; j < n; j++) {
22
      if (pali(i, j, s)) {
23
        int cost = 1 + cut(s, j + 1, n, dp);
24
        min = Math.min(min, cost);
25
      }
26
    }
27

28
    return dp[i] = min;
29
  }
30

31
  public int minCut(String s) {
32
    int n = s.length();
33
    dp = new int[n];
34
    Arrays.fill(dp, -1);
35

36
    return cut(s, 0, n, dp) - 1;
37
  }
38
}