C++刷leetcode（1278. 分割回文串 III）【动态规划】

糖逗

题目描述：

给你一个由小写字母组成的字符串 s，和一个整数 k。

请你按下面的要求分割字符串：

首先，你可以将 s 中的部分字符修改为其他的小写英文字母。
接着，你需要把 s 分割成 k 个非空且不相交的子串，并且每个子串都是回文串。
请返回以这种方式分割字符串所需修改的最少字符数。

 

示例 1：

输入：s = "abc", k = 2
输出：1
解释：你可以把字符串分割成 "ab" 和 "c"，并修改 "ab" 中的 1 个字符，将它变成回文串。
示例 2：

输入：s = "aabbc", k = 3
输出：0
解释：你可以把字符串分割成 "aa"、"bb" 和 "c"，它们都是回文串。
示例 3：

输入：s = "leetcode", k = 8
输出：0
 

提示：

1 <= k <= s.length <= 100
s 中只含有小写英文字母。

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/palindrome-partitioning-iii
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

class Solution {
public:
    int cost(string& s, int left, int right){
        int res = 0;
        for(int i = left, j = right; i < j; i++, j--){
            if(s[i] != s[j]) res++;
        }
        return res;
    } 


    int palindromePartition(string& s, int k){
        int len = s.size();
        vector<vector<int> > dp(len + 1, vector<int>(k + 1, INT_MAX));
        dp[0][0] = 0;
        for(int i = 1; i <= len; i++){
            for(int j = 1; j <= min(k, i); j++){
                if(j == 1) dp[i][j] = cost(s, 0, i-1);
                else{
                    for(int m = j-1; m < i; m++){
                        dp[i][j] = min(dp[i][j], dp[m][j-1] + cost(s, m, i-1)); 
                    } 
                    
                }
            }
        } 
        return dp[len][k];
    } 
};

参考链接：https://leetcode-cn.com/problems ... -leetcode-solution/

糖逗

还是不太懂动态规划套路的一天