C++, Top-Down Memoization, Clear
To Reduce run time, I precomputed the number of changes required to make a string palindromic between start and end value, where start and end can be any value 
To Reduce run time, I precomputed the number of changes required to make a string palindromic between start and end value, where start and end can be any value between 0 to n-1 inclusive. \nAfter that, It is obvious recursion. I recommend solving [Palindrome Partition II](http://https://leetcode.com/problems/palindrome-partitioning-ii/) before this\n```\nclass Solution {\npublic:\n    int dp[101][101]; \n    vector<vector<int>> PR;\n    \n    void findRequired(int start, int end, string s){\n        while (start >= 0 && end < s.size()){\n            if(start == end) PR[start][end] = 0; \n            else if(s[start] == s[end]) PR[start][end] = PR[start+1][end-1];            \n            else PR[start][end] = 1+PR[start+1][end-1]; \n            start--, end ++; \n        }\n        \n    }\n    int memo(string s, int start , int k){\n        if(k == 0) return PR[start][s.size()-1]; \n        if(start == s.size()-1) return 1e9; \n        if(dp[start][k] != -1) return dp[start][k]; \n        int res = INT_MAX ;\n        for(int i=start; i<s.size()-1; i++){\n            int temp  = PR[start][i]+ memo(s, i+1, k-1); \n            res = min(res, temp ); \n        }\n        return dp[start][k] = res; \n    }\n    int palindromePartition(string s, int k) {\n        memset(dp, -1, sizeof(dp)); \n        int n = s.size(); \n        PR.resize(n+1, vector<int>(n+1, 0));\n        \n        for(int i=0; i< n; i++){\n            findRequired(i,i,s); \n            findRequired(i,i+1, s); \n        }\n        return memo(s,0,k-1); \n    }\n};\n```
['Memoization', 'C']