C++, SIMPLE PARTITIONING DP WITH PALINDROME LOGIC
Intuition\n Describe your first thoughts on how to solve this problem. \n\n# Approach\nWe have to split the string into k non empty disjoint substrings such tha
# Intuition\n<!-- Describe your first thoughts on how to solve this problem. -->\n\n# Approach\nWe have to split the string into k non empty disjoint substrings such that after changing any number of characters of the k substrings, all of them are palindromes. We maintain an iterator as well as a count of the splits. Our base case will return 0 only when the count of our splits is equal to K. I have taken K as m in my recursive function. O/W, we will return 1e9 to represent invalid case where we have more than k number of splits. Whenever we split, we call the change function to get the ans to the number of characters needed to be changed if the substring being split is not a palindrome. Simply keep two pointers and traverse the string from the front and the back. Whenever, s[i] != s[j], we increment our ans as we will have to change one of s[i] or s[j] to make the substring a palindrome. We maintain an ans to track the minimum ans at every sub problem. We apply 2-D DP to reduce time compexity to O(n * k).\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```\nclass Solution {\npublic:\n\n    int dp[101][101];\n\n    int change(int i, int j, string &s) {\n\n        int ans = 0;\n\n        while(i < j) {\n\n            if(s[i] != s[j]) ans++;\n\n            i++;\n\n            j--;\n        }\n\n        return ans;\n    }\n\n    int solve(int i, int k, string &s, int m, int n) {\n\n        if(i >= n) {\n\n            if(k == m) return 0;\n\n            return 1e9;\n        }\n\n        if(dp[i][k] != -1) return dp[i][k];\n\n        int ans = 1e9;\n\n        for(int j = i; j < n; j++) {\n\n            if(k + 1 <= m) {\n\n                ans = min(ans, change(i, j, s) + solve(j + 1, k + 1, s, m, n));\n            }\n        }\n\n        return dp[i][k] = ans;\n    }\n    \n    int palindromePartition(string s, int k) {\n\n        int n = s.length();\n\n        memset(dp, -1, sizeof dp);\n\n        return solve(0, 0, s, k, n);\n        \n    }\n};\n```
['C++']