Simple DP Solution || JAVA || Memoization || 71%
Intuition\n Describe your first thoughts on how to solve this problem. \n\n# Approach\n Describe your approach to solving the problem. \nstore number of chars n
# Intuition\n<!-- Describe your first thoughts on how to solve this problem. -->\n\n# Approach\n<!-- Describe your approach to solving the problem. -->\nstore number of chars need to be changes between index i, j in 2d array and find all possible scenario with brute force approach and latter do memoization to prevent duplicate calculation\n\n# Complexity\n- Time complexity:\n<!-- Add your time complexity here, e.g. $$O(n)$$ -->\n\n- Space complexity:\n<!-- Add your space complexity here, e.g. $$O(n)$$ -->\n\n# Code\n\n/************* PLEASE UPVOTE *****************/\n```\nclass Solution {\n    static int M = Integer.MAX_VALUE;\n    int[][] dp;\n    int[][] palCount;\n    public int palindromePartition(String s, int k) {\n        dp = new int[s.length()][k+1];\n        palCount = new int[s.length()][s.length()+1];\n        for(int i=0; i<s.length();i++) {\n            Arrays.fill(dp[i], -1);\n            for(int j=i+1; j<=s.length(); j++) {\n                palCount[i][j] = makePalindrome(s.substring(i,j));\n            }\n        }\n\n        return palindromePart(0, k, s);\n    }\n\n    int palindromePart(int index, int k, String s) {\n        if(index==s.length() || k<0) {\n            if(k==0)\n            return 0;\n            return M;\n        }\n        if(dp[index][k]!=-1)\n        return dp[index][k];\n        int ans = M, temp;\n        for(int i=index; i<=s.length()-k; i++) {\n            temp = palindromePart(i+1, k-1, s);\n            if(temp!=M) {\n                temp+=palCount[index][i+1];\n            }\n            ans=Math.min(temp, ans);\n        }\n        return (dp[index][k]=ans);\n    }\n\n    int makePalindrome(String s) {\n        int i=0, j=s.length()-1;\n        int count = 0;\n        while(i<j) {\n            if(s.charAt(i)!=s.charAt(j))\n            count++;\n            i++;\n            j--;\n        }\n        return count;\n    }\n}\n```
['Java']