Javascript solution with explanation 64ms, 85%
\n/*\t\n The idea is to fill two grids:\n  - mins[i][j] is minimum number of chars changes needed to make substring (i to j) a palindrome:\n  - dp[i][k] is the 
```\n/*\t\n The idea is to fill two grids:\n  - mins[i][j] is minimum number of chars changes needed to make substring (i to j) a palindrome:\n  - dp[i][k] is the number of changes needed to be performed with substring s.slice(0, i + 1) in order to split that substring to k palindromes \n Filling each dp cell would be possible having mins and previous dp row precalculated\n\n Filling mins:\n \t1. mins[i][i] = 0; because all one-length strings are palindromes;\n \t2. mins[i][i + 1] = mins[i][i + 1] = s[i] === s[i + 1] ? 0 : 1; any two-length substring will have only 1 or 0 chars replace in order to be a palindrome, 1 if chars are not the same and 0 if they are the same\n \t3. calculate all other min[i][j] according the rule that min[i][j] = min[i + 1][j - 1] + (s[left] === s[right] ? 0 : 1); min of inner substring changes + 1 if leftmost and rightmost chars are not the same\nFilling dp: \n    1. dp[0][k] = 0; substring s.slice(0, 1) will always be palindrome so k is ignored for substrings of length 1;\n    2. dp[i][1] = mins[0][i]; since mins[0][i] - is minimum number of chars changes needed to make substring (0 to i) a palindrome we can fill dp[i][1]\n    3. dp[i][k] = Math.min(dp[i][k], dp[j][k - 1] + mins[j + 1][i]); to fill all other dp[i][j] we loop through all k starting from 2 and finishing with K, and for each k we loop through all string indexes from 1 to the end, and inside we make 3rd loop to to compare each possible options to find min\n \n * @param {string} s\n * @param {number} k\n * @return {number}\n */\nconst palindromePartition = (s, K) => {\n\tif (s.length === K) return 0;\n\tconst mins = new Array(s.length).fill(0).map((s) => []);\n\tconst dp = new Array(s.length).fill(0).map((s) => []);\n\n\tfor (let i = 0; i < s.length; i++) {\n\t\tmins[i][i] = 0;\n\t\tmins[i][i + 1] = s[i] === s[i + 1] ? 0 : 1;\n\t}\n\n\tfor (let i = 0; i < s.length; i++) {\n\t\tfor (let j = i + 2; j < s.length; j++) {\n\t\t\tmins[i][j] = calcMin(s, i, j);\n\t\t}\n\t}\n\n\tfor (let k = 1; k <= K; k++) dp[0][k] = 0;\n\tfor (let i = 0; i < s.length; i++) dp[i][1] = mins[0][i];\n\n\tfor (let k = 2; k <= K; k++) {\n\t\tfor (let i = 1; i < s.length; i++) {\n\t\t\tdp[i][k] = Infinity;\n\t\t\tfor (let j = 0; j < i; j++) {\n\t\t\t\tdp[i][k] = Math.min(dp[i][k], dp[j][k - 1] + mins[j + 1][i]);\n\t\t\t}\n\t\t}\n\t}\n\n\treturn dp[s.length - 1][K];\n\n\tfunction calcMin(s, left, right) {\n\t\tif (mins[left][right] !== undefined) return mins[left][right];\n\t\treturn calcMin(s, left + 1, right - 1) + (s[left] === s[right] ? 0 : 1);\n\t}\n};\n```
[]