[C++] 0 ms, dp: explained how to build up the dp, detailed hints + graph
Hints:\n - if len == k, the cost is 0\n - if k==1, the cost is the cost to make the substring [0...right] a palindrome\n - the cost of making a palindrome is al
Hints:\n - if ```len == k```, the cost is ```0```\n - if ```k==1```, the cost is the cost to make the substring ```[0...right]``` a palindrome\n - the cost of making a palindrome is always less than ```len``` so len can be used as an init value\n - we can come up with the same ```left``` and ```right``` positions for different parts, so lets\' keep them in dp, let\'s call it ```dplr```\n - build up the best combo for ```k``` parts in ```dpres```:\n    -  ```dp[parts][right]``` = minimal number of changes if we partition the sub-string ```[0...right]``` into ```[parts]``` parts. \n    -  ```dp[parts][right]``` = ```dp[parts-1][left] + cost of s.substring(left+1, right]``` where ```left``` is in the range ```[0...right]```\n    -  So we check all possible substrings ending at the ```right``` position + take the cost of the remaing substring\n```\n                       <0-------------------------left---------------right> // substring[0,left] >= parts -1 to have at least 1 char per part\ndp[parts][right] = min(    dpres[parts-1][left]    +  dplr[left+1][right]   ) for all possible left\n```\nFor example: s = "aabbc", k = 3\n```\nMath.min( "aa"/k=2 + cost of "bbc",  // left=2, right=4\n          "aab"/k=2 + cost of "bc",  // left=3, right=4\n          "aabb"/k=2 + cost of "c" ) // left=4, right=4\n```\nRun the check for each possible ```left``` value and trigger the recursive call for the remaining left part and ```k-1``` parts.\n\nThis code takes 0 ms, beats 100%\n```\nclass Solution {\npublic:\n    int len;\n    int getCost(string& s, int l, int r, vector<vector<int>>& dplr) {\n        if(l==r) return 0;\n        int cost = dplr[l][r];\n        if(cost<len) return cost;\n        cost = 0;\n        for(int ll=l,rr=r;rr>ll;ll++,rr--)\n            if(s[ll]!=s[rr]) cost++;\n        dplr[l][r] = cost;\n        return cost;\n    }\n    int getPartition(string& s, int k, int r, vector<vector<int>>& dplr, vector<vector<int>>& dpres) {\n        if(k==r+1) return 0;\n        if(k==1) return getCost(s,0,r,dplr);\n        int cost = dpres[r][k];\n        if(cost<len) return cost;\n        \n        // preserve k-1 chars for k-1 remaining parts, 1 char per part\n        for(int l=k-1; l<=r; l++) {\n            cost = min(cost, getPartition(s,k-1,l-1,dplr,dpres)+getCost(s,l,r,dplr));\n        }\n        dpres[r][k] = cost;\n        return cost;\n    }\n    \n    int palindromePartition(string s, int k) {\n        len=s.size();\n        // actual res will be always less than len, so initialize dp with len\n        vector<vector<int>> dplr(len,vector<int>(len,len));  // [left][right] = cost\n        vector<vector<int>> dpres(len,vector<int>(k+1,len)); // [left][k] = cost\n        return getPartition(s,k,len-1,dplr,dpres);\n    }\n};\n```
['Dynamic Programming', 'C']