Java DP with memorization
\nclass Solution {\n    Map<String, Integer> map = new HashMap<>();\n    public int palindromePartition(String s, int k) {\n        if (s.length() == k) return 
```\nclass Solution {\n    Map<String, Integer> map = new HashMap<>();\n    public int palindromePartition(String s, int k) {\n        if (s.length() == k) return 0;\n        int len = s.length();\n        int[][] dp = new int[k][len + 1];\n        for (int i = 0; i < len; ++i){\n            dp[0][i + 1] = helper(s.substring(0, i + 1));\n        }\n        for (int i = 1; i < k; ++i){\n            for (int j = i; j <= len; ++j){\n                int cur = Integer.MAX_VALUE;\n                for (int p = j; p >= i; p--){\n                    cur = Math.min(cur, dp[i - 1][p - 1] + helper(s.substring(p - 1,j )));\n                }\n                dp[i][j] = cur;\n            }\n        }\n        return dp[k - 1][len];\n        \n        \n    }\n    private int helper(String str){\n        if (str == null || str.length() == 0) return 0;\n        if (map.containsKey(str)) return map.get(str);\n        int res = 0;\n        for (int i = 0; i < str.length(); ++i){\n            if (str.charAt(i) != str.charAt(str.length() - i - 1)) res++;\n        }\n        res /= 2;\n        map.put(str, res);\n        return res;\n    }\n}\n```\nthis question essentially is a knapsack problem.  \ndp[i][j] means that the mininal number of change if we partition the string at j  for i-th time.\n
[]