[Java] DP solution with explanation
This is the dp equation(this equation did not consider when k == 0 situation, for the comprehensive equation, plase view the code).\n\ndp[i][j] = Math.min(dp[i 
This is the dp equation(this equation did not consider when k == 0 situation, for the comprehensive equation, plase view the code).\n\ndp[i][j] = Math.min(dp[i - 1][k - 1] + minimum[k][j]);\n\nThe whole 2D array represents the number of changes needed to form i palindromes from the index of  0 to k - 1. The array minimum represents the number of changes needed to form a palindrome from the index of k to j. We base on this equation to increase the number of palindromes.\nThat is the key idea, if you still don\'t get it, pls leave your question.\n```\nclass Solution {\n    public int palindromePartition(String s, int k) {\n        int n = s.length();\n        int[][] minimum = new int[n][n];\n        for (int i = 0; i < n; i++) {\n            for (int j = 0; j <= i; j++) {\n                minimum[j][i] = mini_change(s, j, i);\n            }\n        }\n        int[] previous = new int[n];\n        for(int i = 0; i < n; i ++) previous[i] = minimum[0][i];\n        for (int time = 1; time < k; time++) {\n            int[] current = new int[n];\n            Arrays.fill(current, Integer.MAX_VALUE);\n            for (int i = 0; i < n; i++) {\n                for(int j = 0; j <= i; j++){\n                    if(j == 0) current[i] = Math.min(current[i], minimum[0][i]);\n                    else current[i] = Math.min(current[i], previous[j - 1] + minimum[j][i]);\n                }\n            }\n            previous = current;\n        }\n        return previous[n - 1];\n    }\n\n    public int mini_change(String s, int left, int right){\n        int count = 0;\n        while(left < right){\n            if(s.charAt(left) != s.charAt(right)) count += 1;\n            left += 1;\n            right -= 1;\n        }\n        return count;\n    }\n}
[]