[Java] Recursion -> Memoization -> Tabulation | O(n * n * k) time
Approach\nFirst, we will try to find out the minimum number of characters change required to make a substring palindrome.\nWe\'ll check all the possible substri
# Approach\nFirst, we will try to find out the minimum number of characters change required to make a substring palindrome.\nWe\'ll check all the possible substrings of the given string and store the above mentioned cost in a storage.\nThen, for a particular length of string and a particular number of cuts, we will try to find the answer by trying all the possible combinations of partitioning.\nLet\'s see how...\n\n# Recursion (TLE)\n\nThe recursive solution will give TLE as expected.\n\n```\nclass Solution {\n    public int palindromePartition(String s, int k) {\n        int n = s.length();\n        int[][] dp = new int[n][n];\n\n        for (int gap = 0; gap < n; gap++) {\n            for (int i = 0, j = gap; j < n; i++, j++) {\n                if (gap == 0) {\n                    dp[i][j] = 0;\n                } else {\n                    dp[i][j] = s.charAt(i) == s.charAt(j) ? 0 : 1;\n                    if (gap > 1) {\n                        dp[i][j] += dp[i + 1][j - 1];\n                    }\n                }\n            }\n        }\n\n        return palindromePartitioning(s, 0, k - 1, dp);\n    }\n\n    private int palindromePartitioning(String s, int i, int cuts, int[][] dp) {\n        if (cuts == 0) {\n            return dp[i][s.length() - 1];\n        }\n\n        int min = Integer.MAX_VALUE;\n\n        for (int j = i; j < s.length() - cuts; j++) {\n            min = Math.min(min, dp[i][j] + palindromePartitioning(s, j + 1, cuts - 1, dp));\n        }\n\n        return min;\n    }\n}\n```\n\n# Memoization (DP) (Accepted)\n\n- Time complexity: O(n * n * k)\n- Space complexity: O(n * n)\n\n```\nclass Solution {\n    public int palindromePartition(String s, int k) {\n        int n = s.length();\n        int[][] dp = new int[n][n];\n\n        for (int gap = 0; gap < n; gap++) {\n            for (int i = 0, j = gap; j < n; i++, j++) {\n                if (gap == 0) {\n                    dp[i][j] = 0;\n                } else {\n                    dp[i][j] = s.charAt(i) == s.charAt(j) ? 0 : 1;\n                    if (gap > 1) {\n                        dp[i][j] += dp[i + 1][j - 1];\n                    }\n                }\n            }\n        }\n\n        return palindromePartitioning(s, 0, k - 1, dp, new Integer[n][k]);\n    }\n\n    private int palindromePartitioning(String s, int i, int cuts, int[][] dp, Integer[][] memo) {\n        if (cuts == 0) {\n            return dp[i][s.length() - 1];\n        }\n\n        if (memo[i][cuts] != null) {\n            return memo[i][cuts];\n        }\n\n        int min = Integer.MAX_VALUE;\n\n        for (int j = i; j < s.length() - cuts; j++) {\n            min = Math.min(min, dp[i][j] + palindromePartitioning(s, j + 1, cuts - 1, dp, memo));\n        }\n\n        return memo[i][cuts] = min;\n    }\n}\n```\n\n# Tabulation (DP) (Accepted)\n\n- Time complexity: O(n * n * k)\n- Space complexity: O(n * n)\n\n```\nclass Solution {\n    public int palindromePartition(String s, int k) {\n        int n = s.length();\n        int[][] minChars = new int[n][n];\n\n        for (int gap = 0; gap < n; gap++) {\n            for (int i = 0, j = gap; j < n; i++, j++) {\n                if (gap == 0) {\n                    minChars[i][j] = 0;\n                } else {\n                    minChars[i][j] = s.charAt(i) == s.charAt(j) ? 0 : 1;\n                    if (gap > 1) {\n                        minChars[i][j] += minChars[i + 1][j - 1];\n                    }\n                }\n            }\n        }\n\n        int[][] dp = new int[n][k];\n\n        for (int j = 0; j < n; j++) {\n            for (int cuts = 0; cuts <= Math.min(j, k - 1); cuts++) {\n                if (cuts == 0) {\n                    dp[j][cuts] = minChars[0][j];\n                } else {\n                    int min = Integer.MAX_VALUE;\n                    for (int i = j; i >= cuts; i--) {\n                        min = Math.min(min, dp[i - 1][cuts - 1] + minChars[i][j]);\n                    }\n                    dp[j][cuts] = min;\n                }\n            }\n        }\n\n        return dp[n - 1][k - 1];\n    }\n}\n```
['Dynamic Programming', 'Memoization', 'Java']