1
class Solution {
2
 public:
3
  // function to precompute if every substring of s is a palindrome or not
4
  vector<vector<bool>> isPalindrome(string &s) {
5
    int n = s.size();
6
    vector<vector<bool>> dp(n, vector<bool>(n, false));
7

8
    for (int i = 0; i < n; i++) {
9
      dp[i][i] = true;
10
    }
11

12
    for (int i = 0; i < n - 1; i++) {
13
      if (s[i] == s[i + 1]) {
14
        dp[i][i + 1] = true;
15
      }
16
    }
17

18
    int k = 2;
19

20
    while (k < n) {
21
      int i = 0;
22
      int j = k;
23

24
      while (j < n) {
25
        if (s[i] == s[j] and dp[i + 1][j - 1]) {
26
          dp[i][j] = true;
27
        }
28

29
        i++;
30
        j++;
31
      }
32

33
      k++;
34
    }
35

36
    return dp;
37
  }
38

39
  // function to find the minimum palindromic substrings in s
40
  int solve(string &s, int n, int i, vector<vector<bool>> &palin, vector<int> &memo) {
41
    if (i == n) {
42
      return 0;
43
    }
44
    if (memo[i] != -1) {
45
      return memo[i];
46
    }
47

48
    int result = INT_MAX;
49

50
    for (int j = i + 1; j <= n; j++) {
51
      if (palin[i][j - 1]) {
52
        result = min(result, 1 + solve(s, n, j, palin, memo));
53
      }
54
    }
55

56
    return memo[i] = result;
57
  }
58

59
  int minCut(string s) {
60
    int n = s.size();
61
    vector<int> memo(n, -1);
62
    vector<vector<bool>> palin = isPalindrome(s);
63
    return solve(s, n, 0, palin, memo) - 1;
64
  }
65
};