1
class Solution {
2
 public:
3
  int dp[105][105];
4
  /// Count Number of changes to be done
5
  /// to make substring of s from i to j
6
  /// to palindrome
7
  int changes(int i, int j, string &s) {
8
    int cnt = 0;
9
    while (i < j) {
10
      cnt += (s[i++] != s[j--]);
11
    }
12
    return cnt;
13
  }
14

15
  int recur(int idx, int k, string &s) {
16
    /// If Reached end of s and found partions to be done 0
17
    /// return 0 , otherwise return INT_MAX/any big number
18
    if (idx == s.size()) {
19
      return (k == 0) ? 0 : 1e7;
20
    }
21

22
    /// Partitions to be done have completed , but
23
    /// we are not at the end of the string
24
    /// return INT_MAX/any big number
25
    if (k == 0) {
26
      return 1e7;
27
    }
28

29
    if (dp[idx][k] != -1) {
30
      return dp[idx][k];
31
    }
32

33
    /// Partitioning the String
34
    int ans = INT_MAX;
35
    for (int i = idx; i < s.size(); i++) {
36
      ans = min(ans, changes(idx, i, s) + recur(i + 1, k - 1, s));
37
    }
38
    return dp[idx][k] = ans;
39
  }
40

41
  int palindromePartition(string s, int k) {
42
    /// Edge Case
43
    if (k == s.size()) {
44
      return 0;
45
    }
46
    memset(dp, -1, sizeof(dp));
47
    return recur(0, k, s);
48
  }
49
};