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 != s) 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;
for(int i = 1; i <= len; i++){
for(int j = 1; j <= min(k, i); j++){
if(j == 1) dp = cost(s, 0, i-1);
else{
for(int m = j-1; m < i; m++){
dp = min(dp, dp + cost(s, m, i-1));
}
}
}
}
return dp;
}
};
参考链接：https://leetcode-cn.com/problems/palindrome-partitioning-iii/solution/fen-ge-hui-wen-chuan-iii-by-leetcode-solution/ 还是不太懂动态规划套路的一天{:10_255:}
页:
[1]