1
var palindromePartition = function (s, k) {
2
  const len = s.length;
3

4
  const cost = (i = 0, j = 0) => {
5
    let c = 0;
6
    while (i <= j) {
7
      if (s[i] != s[j]) c++;
8
      i++, j--;
9
    }
10
    return c;
11
  };
12

13
  const dp = Array.from({ length: len }, () => {
14
    return new Array(k + 1).fill(-1);
15
  });
16

17
  const splitHelper = (idx = 0, sl = k) => {
18
    if (sl < 0) return Infinity;
19
    if (idx == len) {
20
      if (sl == 0) return 0;
21
      return Infinity;
22
    }
23

24
    if (dp[idx][sl] != -1) return dp[idx][sl];
25

26
    let ans = Infinity;
27

28
    for (let i = idx; i < len; i++) {
29
      ans = Math.min(ans, splitHelper(i + 1, sl - 1) + cost(idx, i));
30
    }
31
    return (dp[idx][sl] = ans);
32
  };
33

34
  return splitHelper();
35
};