C++ Bottom up DP solution
The question asks us to find the minimum number of changes we have to perform so that we can divide the string into k palindromic substrings. \n\nTo do this, we
The question asks us to find the minimum number of changes we have to perform so that we can divide the string into k palindromic substrings. \n\nTo do this, we can use dynamic programming. Define dp[i][j] = Minimum number of changes to be performed in s[0...i] so that we can divide it into exactly j palindromic substrings. \n\nNow, what is the transition function? Well, that\'s quite simple. Consider some k < i. If we know the value of dp[k][j - 1], can we say something about dp[i][j]? Yes, definitely, but, we need some more information to calculate dp[i][j] from dp[k][j - 1]. That is the number of changes to be made in the string s[k + 1...i] so that it becomes a palindrome. And, we need to minimize this over all k. But, how to calculate the extra information that we needed efficiently? \n\nAgain, the answer is (no surprises here) DP. \nConsider no_of_changes[i][j] = Number of changes to be made in s[i...j] so that it becomes a palindrome. \nWhat are the base cases? no_of_changes[i][i] = 0(1- letter string is a palindrome), no_of_changes[i][i + 1] = (0 or 1) depending on whether s[i] and s[i + 1] are equal or not. \nWhat is the transition function here? no_of_changes[i][j] = no_of_changes[i + 1][j - 1] + (s[i] != s[j]) \n\nOnce that is done, we can use it in our first DP, and the final answer will be dp[n - 1][k].  The C++ implementation of this idea can be found below:\n\n```\nclass Solution {\npublic:\n    const int INF = (int)1e9;\n    int palindromePartition(string s, int k) {\n        int n = s.size();\n        \n        int to_change[n][n];\n        memset(to_change, false, sizeof(to_change));\n        \n        for (int i = 0; i < n; ++i) {\n            to_change[i][i] = 0;\n        }\n        for (int i = 0; i + 1 < n; ++i) {\n            to_change[i][i + 1] = (s[i] != s[i + 1]);\n        }\n        \n        for (int len = 3; len <= n; ++len) {\n            for (int i = 0; i + len - 1 < n; ++i) {\n                to_change[i][i + len - 1] = to_change[i + 1][i + len - 2] + (s[i] != s[i + len - 1]);\n            }\n        }\n        \n        int dp[n][k + 1];\n        // dp[i][j] = min. changes to split s[0..i] into exactly j parts.\n        // dp[i][j] = min_{k < i}(dp[k][j - 1] + to_change[k + 1][i])\n        for (int i = 0; i < n; ++i) {\n            for (int j = 0; j <= k; ++j) {\n                dp[i][j] = INF;\n            }\n        }\n        \n        for (int i = 0; i < n; ++i) {\n            dp[i][1] = to_change[0][i];\n        }\n        \n        for (int num_parts = 2; num_parts <= k; ++num_parts) {\n            for (int i = num_parts - 1; i < n; ++i) {\n                for (int j = i - 1; j >= 0; --j) {\n                    dp[i][num_parts] = min(dp[i][num_parts], dp[j][num_parts - 1] + to_change[j + 1][i]);\n                }\n            }\n        }\n        \n        return dp[n - 1][k];\n    }\n};\n```
[]