[Clean] | DP - Memoization | O(N^3*K) to O(N^2*K)
\nclass Solution {\n    string _s;\n    int len;\n    int dp[101][101];\n    int cost[101][101];\n    int change(int start, int end){\n        int cost=0;\n    
```\nclass Solution {\n    string _s;\n    int len;\n    int dp[101][101];\n    int cost[101][101];\n    int change(int start, int end){\n        int cost=0;\n        while(start<end){\n            cost+=_s[start]!=_s[end];\n            start++;end--;\n        }\n        return cost;\n    }\n    void createCost(){\n        for(int l=1;l<=len;l++){\n            for(int start=0,end=start+l-1;end<len;start++,end++){\n                if(l==1)\n                    cost[start][end]=0;\n                else if(l==2)\n                    cost[start][end]=_s[start]!=_s[end];\n                else\n                    cost[start][end]=(_s[start]!=_s[end])+cost[start+1][end-1];\n            }\n        }\n    }\n    int dfs(int idx, int k){//n^2\n        if(idx>=len)\n            return 0;\n        if(k==1)\n            // return change(idx,len-1);\n            return cost[idx][len-1];\n        if(dp[idx][k]!=-1)\n            return dp[idx][k];\n        int c=INT_MAX;\n        for(int i=idx;i<=len-k;i++){//n\n            // c=min(change(idx,i)+dfs(i+1,k-1),c);//n\n            c=min(cost[idx][i]+dfs(i+1,k-1),c);//1\n        }\n        return dp[idx][k]=c;\n    }\npublic:\n    int palindromePartition(string s, int k) {\n        _s=s;\n        len=s.size();\n        memset(dp,-1,sizeof(dp));\n        createCost();\n        return dfs(0,k);\n    }\n};\n```
['Dynamic Programming', 'Recursion', 'Memoization', 'C', 'C++']