C++ Top-Down DP
\nclass Solution {\npublic:\n    int palindromePartition(string s, int k) {\n        n = s.size();\n        this->s = move(s);\n\n        return getdp(0, k);\n 
```\nclass Solution {\npublic:\n    int palindromePartition(string s, int k) {\n        n = s.size();\n        this->s = move(s);\n\n        return getdp(0, k);\n    }\n\nprivate:\n    int getdp(int i, int k) {\n        if (dp[i][k] != -1) {\n            return dp[i][k];\n        }\n\n        if (n - i < k) {\n            return dp[i][k] = inf;\n        }\n        \n        if (k == 1) {\n            return dp[i][k] = getChange(i, n - 1);\n        }\n\n        int ans = INT_MAX;\n        for (int j = i; j <= n - k; ++j) {\n            ans = min(ans, getChange(i, j) + getdp(j + 1, k - 1));\n        }\n        \n        return dp[i][k] = ans;\n    }\n    \n    int getChange(int i, int j) {\n        if (change[i][j] != -1) {\n            return change[i][j];\n        }\n        \n        if (i >= j) {\n            return change[i][j] = 0;\n        }\n        \n        return (s[i] == s[j] ? 0 : 1) + getChange(i + 1, j - 1);\n    }\n\n    int inf = 1000000;\n    int n;\n    string s;\n    vector<vector<int>> dp{101, vector<int>(101, -1)};\n    vector<vector<int>> change{101, vector<int>(101, -1)};\n};\n```
[]