[Java] 4ms DP with memorization + explanation
Basic idea: dp[i][j] = minimal number of changes if we partition the sub-string[0:j] into [i] parts. dp[i][j] can be calculated using the min value of [dp[i-1][
Basic idea: dp[i][j] = minimal number of changes if we partition the sub-string[0:j] into [i] parts. dp[i][j] can be calculated using the min value of [dp[i-1][p] + cost of s.substring(p+1, j] where p in(0:j)\nFor example: s = "aabbc", k = 3\n```\nMath.min( "aa"/k=2 + cost of "bbc",\n          "aab"/k=2 + cost of "bc",\n          "aabb"/k=2 + cost of "c" )\n```\n\n```\npublic int palindromePartition(String s, int k) {\n        int len = s.length();\n        if (len <= k) return 0;\n\n        int[][] dp = new int[k][len];\n        int[][] cache = new int[len][len]; // caching the cost of s.substring(left, right)\n        char[] chars = s.toCharArray();  // optimization: avoid calling substrings\n\n        // initialize cache\n        for (int i = 0; i < len; ++i) {\n            for (int j = i; j < len; ++j) { // optimization: j is always >= i\n                cache[i][j] = -1;\n            }\n        }\n\n        for (int i = 0; i < k; ++i) {\n            for (int j = i; j < len; ++j) {\n                if (i == 0) {\n                    dp[i][j] = cost(chars, i, j, cache); // k = 1\n                } else {\n                    int min = Integer.MAX_VALUE;\n                    for (int p = i; p <= j; ++p) {\n                        min = Math.min(min, dp[i - 1][p - 1] + cost(chars, p, j, cache));\n                    }\n                    dp[i][j] = min;\n                }\n            }\n        }\n\n        return dp[k - 1][len - 1];\n    }\n\n    protected int cost(char[] s, int left, int right, int[][] cache) {\n        if (cache[left][right] != -1) return cache[left][right];\n\n        int diff = 0, ll = left, rr = right;\n        while (ll < rr) {\n            if (s[ll++] != s[rr--]) diff++;\n        }\n\n        return cache[left][right] = diff;\n    }\n```
['Dynamic Programming', 'Memoization']