[C++] bottom up DP solution
\nclass Solution {\npublic:\n    int dp[101][101][101];\n    int f(string s,int i,int j,int k,vector< vector<int> >&predp){\n        if(j-i+1<k){\n            r
```\nclass Solution {\npublic:\n    int dp[101][101][101];\n    int f(string s,int i,int j,int k,vector< vector<int> >&predp){\n        if(j-i+1<k){\n            return 10000;\n        }\n        int ans = 10000;\n        if(k==1){\n            dp[i][j][k] = predp[i][j];\n        }\n        if(dp[i][j][k]!=-1){\n            return dp[i][j][k];\n        }\n        for(int idx=i+1;idx<=j;idx++){\n            ans = min(ans,predp[i][idx-1]+f(s,idx,j,k-1,predp));\n        }\n        dp[i][j][k] = ans;\n        return ans;\n    }\n    int palindromePartition(string s, int k) {\n        int n = s.size();\n        memset(dp,-1,sizeof(dp));\n        if(n<=k){\n            return 0;\n        }\n        vector< vector<int> >predp(n,vector<int>(n,0));\n        for(int i=0;i<n;i++){\n            predp[i][i]=0;\n        }\n        for(int len=2;len<=n;len++){\n            for(int i=0;i<=n-len;i++){\n                int j = i+len-1;\n                if(len==2){\n                    predp[i][j]= (s[i]==s[j])?0:1;\n                } else {\n                    predp[i][j] = predp[i+1][j-1];\n                    predp[i][j] += (s[i]==s[j])?0:1;\n                }\n            }\n        }\n        f(s,0,n-1,k,predp);\n        return dp[0][n-1][k];\n    }\n};\n```
[]