simple c++ solution using memoization
Intuition\nThe problem is about partitioning a given string into exactly k non-empty substrings such that the sum of changes required to make each substring a p
# Intuition\nThe problem is about partitioning a given string into exactly `k` non-empty substrings such that the sum of changes required to make each substring a palindrome is minimized. The idea is to use dynamic programming to solve this problem efficiently.\n\n# Approach\n1. **Palindrome Change Calculation**:\n   - Use a 2D DP array `memo` where `memo[start][end]` stores the minimum number of changes required to make the substring `s[start:end+1]` a palindrome.\n   - The helper function `excCount` calculates this value recursively, and uses memoization to avoid redundant calculations.\n\n2. **Partitioning with DP**:\n   - Use another 2D DP array `dp` where `dp[ind][count]` represents the minimum changes required to partition the substring `s[ind:n]` into `count` palindromic substrings.\n   - The recursive function `sol` tries to partition the substring starting from index `ind` into `k` parts, and uses the `memo` array to calculate the number of changes for each potential partition.\n   - It returns the minimum number of changes required to partition the string into `k` palindromic substrings.\n\n3. **Base and Recursive Cases**:\n   - Base case: If the substring is already partitioned into `k` substrings, return the changes needed for the remaining substring.\n   - Recursive case: Try every possible partitioning of the substring and take the minimum.\n\n# Complexity\n- **Time complexity**:\n  - Calculating palindrome changes for all substrings takes \\(O(n^2)\\).\n  - Partitioning with DP takes \\(O(n^2 \\cdot k)\\).\n  - Overall: \\(O(n^2 \\cdot k)\\).\n\n- **Space complexity**:\n  - The memoization arrays `memo` and `dp` each take \\(O(n^2)\\) and \\(O(n \\cdot k)\\) space respectively.\n  - Overall: \\(O(n^2 + n \\cdot k)\\).\n\n# Code\n```cpp\nclass Solution {\npublic:\n    int n;\n    vector<vector<int>> memo;\n    vector<vector<int>> dp;\n\n    int excCount(string &s, int start, int end) {\n        if (start >= end) return 0;\n        if (memo[start][end] != -1) return memo[start][end];\n        return memo[start][end] = (s[start] != s[end]) + excCount(s, start + 1, end - 1);\n    }\n\n    int sol(string &s, int k, int ind, int count) {\n        if (ind == n) return 0;\n        if (dp[ind][count] != -1) return dp[ind][count];\n        int ans = 1e9;\n        if (count == k - 1) return excCount(s, ind, n - 1);\n        for (int i = ind; i < n - (k - count - 1); i++) {\n            ans = min(ans, excCount(s, ind, i) + sol(s, k, i + 1, count + 1));\n        }\n        return dp[ind][count] = ans;\n    }\n\n    int palindromePartition(string s, int k) {\n        n = s.size();\n        dp.resize(n + 1, vector<int>(k + 1, -1));\n        memo.resize(n + 1, vector<int>(n + 1, -1));\n        return sol(s, k, 0, 0);\n    }\n};\n```\n
['String', 'Dynamic Programming', 'Memoization', 'C++']