Easy dynamic programming solution
First compute the cost for each substring to become a palindrome. Then construct O(n * k) dp with the help of the cost array. Overall time complexity is O(n^2 *
First compute the cost for each substring to become a palindrome. Then construct O(n * k) dp with the help of the cost array. Overall time complexity is O(n^2 * k), space complexity O(n * (n + k)). \n```\nclass Solution {\n\npublic:\n    int palindromePartition(string s, int k) {\n\t\tconst int inf = 1000000;\n        int n = (int) s.size();\n        vector<vector<int>> cost(n, vector<int>(n, 0));\n        for(int i = 0; i < n; ++i) cost[i][i] = 0;\n        for(int len = 1; len < n; ++len) {\n            for(int i = 0; i + len < n; ++i) \n                cost[i][i + len] = len == 1 ? s[i] != s[i + len] : (cost[i + 1][i + len - 1]) + (s[i] != s[i + len]);\n        \n        vector<vector<int>> dp(n + 1, vector<int>(k + 1, inf));\n        dp[n][k] = 0;\n        for(int i = n - 1; i >= 0; --i) \n            for(int j = k - 1; j >= 0; --j) \n                for(int pos = i; pos < n; ++pos) \n                    dp[i][j] = min(dp[i][j], cost[i][pos] + dp[pos + 1][j + 1]);\n       \n        return dp[0][0];\n    }\n};\n```\n\nFeel free to give +1 if you understood and liked the approach :)
[]