C++ Intuitive Solution Recursion With Memoization
We create 2 dp arrays \n1) pal[i][j] = min changes to convert i....j to palindrome\n2) dp[i][k] = min changes to convert to divide the string with k substrings 
We create 2 dp arrays \n1) pal[i][j] = min changes to convert i....j to palindrome\n2) dp[i][k] = min changes to convert to divide the string with k substrings and till ith index.\n\n* If we are at ith index, then we can make a partition at any index from i to string length. Let\'s say we make a partition at index j >= i\n* It\'s cost would be pal[i][j]. Now we are left with the subproblem from index j + 1 to string length with one less partition required\n\n\n```\nclass Solution {\npublic:\n    int pal[101][101];\n    int dp[101][101];\n    int f(string s, int i, int k) {\n        if(i >= s.size())\n            return ((k == 0) ? 0 : 1011);\n        int ans = 1011;\n        if(k < 0)\n            return ans;\n        if(dp[i][k] != -1)\n            return dp[i][k];\n        for(int l = i; l < s.size(); l++) {\n            ans = min(ans, pal[i][l] + f(s, l + 1, k - 1));\n        }\n        return dp[i][k] = ans;\n    }\n    \n    int dfs(string s, int i, int j) {\n        if(i >= j)\n            return 0;\n        int cnt = 0;\n\t\tif(pal[i][j] != -1)\n\t\t\treturn pal[i][j];\n        if(s[i] != s[j])\n            cnt++;\n        return pal[i][j] = dfs(s, i + 1, j - 1) + cnt;\n    }\n    \n    int palindromePartition(string s, int k) {\n        int n = s.size(); \n        memset(pal, -1, sizeof pal);\n        memset(dp, -1, sizeof dp);\n        for(int i = 0; i < s.size(); i++) {\n            pal[i][i] = 0;\n            for(int j = i + 1; j < s.size(); j++) {\n                if(pal[i][j] == -1) {\n                    pal[i][j] = dfs(s, i, j);\n                }\n            }\n        }\n        return f(s, 0, k);\n    }\n};\n```
[]