C++, DP simple
\nclass Solution {\npublic:\n    \n    int palindromePartition(string s, int k) {\n        \n        int n = s.size();\n        vector<vector<int>> dp1 (n+1,(ve
```\nclass Solution {\npublic:\n    \n    int palindromePartition(string s, int k) {\n        \n        int n = s.size();\n        vector<vector<int>> dp1 (n+1,(vector<int>(n+1,0)));   // number of change s[i...j] to Palindrome\n        vector<vector<int>> dp2 (n+1,(vector<int>(n+1,0)));  // result of palindromePartition(s[i...end], k)\n      \n// gap between i and j like i = 0. then j = 1 gap is 1 so min gap is 1, gap = 0 is 0\n// gap = 10 no need to invetigate as alreday a palindrone \n// check the gap between all index of i and j possible and update then by checking for diff gap of palindrome \n        \n        for (int gap = 1; gap < n; gap++) {      \n            for (int i = 0, j = gap ; i + gap < n; i++,j++) {\n    \n                \n            if (s[i] == s[j])\n                dp1[i][j] = gap>=2 ? dp1[i+1][j-1] : 0;\n            else\n                dp1[i][j] = (gap >=2 ? dp1[i+1][j-1] : 0) + 1;\n                \n            if (j == n - 1)\n                dp2[i][1] = dp1[i][j];\n            }\n            \n        }\n\n// update the dp2 with changes\n// its just like we made a cut at i = 0,1,2,3,... and we have to make such changes to make it palindrome\n        // for (int i = 0; i < n; ++i)\n        //     dp2[i][1] = dp1[i][n-1];\n        \n// we have to make k subgroups so min our dp from 2 subgroups to k      \n\n    for (int K = 2; K <= k; K++) {\n        for (int i = 0; i + K <= s.size(); i++) {\n            dp2[i][K] = INT_MAX;\n            for (int m = i; m + K <= s.size() ; m++) {\n// number of moves to make s[i..end] to K palindromes = \n// min (number of moves to make s[i..m] to 1 palindromes  + number of moves to make s[m+1..end] to K-1 palindromes)\n// for m in [i..end-1]\n// beacasue s[i] must belong to one palindrome\n                dp2[i][K] = min(dp2[i][K], dp1[i][m] + dp2[m+1][K-1]);\n            }\n        }\n    }\n    \n        return dp2[0][k];\n    }\n};\n```\n1 test case failed in this lower one\n```\nclass Solution {\npublic:\n    \n    int palindromePartition(string s, int k) {\n        \n        int n = s.size();\n        vector<vector<int>> change (n+1,(vector<int>(n+1,0)));   // number of change s[i...j] to Palindrome\n        vector<vector<int>> dp (n+1,(vector<int>(n+1,0)));  // result of palindromePartition(s[i...end], k)\n      \n// length between i and j like i = 0. then j = 1 len is 2 so min length is 2 \n// len = 1 no need to invetigate as alreday a palindrone \n// check the length between all index of i and j possible and update then by checking for diff length of palindrome \n        \n        for (int len = 2; len <= n; ++len) {      \n            for (int i = 0; i + len <= n; ++i) {\n                int j = i + len - 1;\n                \n                if (s[i] == s[j])\n                    change[i][j] = change[i+1][j-1];    // no change get the previous one \n                else\n                    change[i][j] = change[i+1][j-1] + 1;      // we have to change add one in previous\n            }\n        }\n\n// update the dp with changes\n// its just like we made a cut at i = 0,1,2,3,... and we have to make such changes to make it palindrome\n        for (int i = 0; i < n; ++i)\n            dp[i][1] = change[i][n-1];\n        \n// we have to make k subgroups so min our dp from 2 subgroups to k      \n        for (int d = 2; d <= k; ++d) {\n            for (int i = 0; i < n; ++i) { \n                dp[i][d] = INT_MAX;   \n                for (int j = i; j < n; ++j)\n                    dp[i][d] = min(dp[i][d], change[i][j] + dp[j+1][d-1]);\n                \n                \n            }\n        }\n    \n        return dp[0][k];\n    }\n};\n\n/*\n\nfor s = "aabbc", k = 3\n\nchange vector \n\n0 0 1 2 2 0 \n0 0 1 1 1 0 \n0 0 0 0 1 0 \n0 0 0 0 1 0 \n0 0 0 0 0 0 \n0 0 0 0 0 0 \n\ninitializing dp vector\n0 2 0 0 0 0 \n0 1 0 0 0 0 \n0 1 0 0 0 0 \n0 1 0 0 0 0 \n0 0 0 0 0 0 \n0 0 0 0 0 0 \n\nfinal dp vector\n0 2 1 0 0 0 \n0 1 1 0 0 0 \n0 1 0 0 0 0 \n0 1 0 0 0 0 \n0 0 0 0 0 0 \n0 0 0 0 0 0 \n\n\n*/\n
['C']