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

糖逗

题目描述：

1. 给你一个由小写字母组成的字符串 s，和一个整数 k。
   
2. 
   
3. 请你按下面的要求分割字符串：
   
4. 
   
5. 首先，你可以将 s 中的部分字符修改为其他的小写英文字母。
   
6. 接着，你需要把 s 分割成 k 个非空且不相交的子串，并且每个子串都是回文串。
   
7. 请返回以这种方式分割字符串所需修改的最少字符数。
   
8. 
   
9.  
   
10. 
    
11. 示例 1：
    
12. 
    
13. 输入：s = "abc", k = 2
    
14. 输出：1
    
15. 解释：你可以把字符串分割成 "ab" 和 "c"，并修改 "ab" 中的 1 个字符，将它变成回文串。
    
16. 示例 2：
    
17. 
    
18. 输入：s = "aabbc", k = 3
    
19. 输出：0
    
20. 解释：你可以把字符串分割成 "aa"、"bb" 和 "c"，它们都是回文串。
    
21. 示例 3：
    
22. 
    
23. 输入：s = "leetcode", k = 8
    
24. 输出：0
    
25.  
    
26. 
    
27. 提示：
    
28. 
    
29. 1 <= k <= s.length <= 100
    
30. s&#160;中只含有小写英文字母。
    
31. 
    
32. 来源：力扣（LeetCode）
    
33. 链接：https://leetcode-cn.com/problems/palindrome-partitioning-iii
    
34. 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

复制代码

1. class Solution {
   
2. public:
   
3.     int cost(string& s, int left, int right){
   
4.         int res = 0;
   
5.         for(int i = left, j = right; i < j; i++, j--){
   
6.             if(s[i] != s[j]) res++;
   
7.         }
   
8.         return res;
   
9.     }
   
10. 
    
11. 
    
12.     int palindromePartition(string& s, int k){
    
13.         int len = s.size();
    
14.         vector<vector<int> > dp(len + 1, vector<int>(k + 1, INT_MAX));
    
15.         dp[0][0] = 0;
    
16.         for(int i = 1; i <= len; i++){
    
17.             for(int j = 1; j <= min(k, i); j++){
    
18.                 if(j == 1) dp[i][j] = cost(s, 0, i-1);
    
19.                 else{
    
20.                     for(int m = j-1; m < i; m++){
    
21.                         dp[i][j] = min(dp[i][j], dp[m][j-1] + cost(s, m, i-1));
    
22.                     }
    
23.                     
    
24.                 }
    
25.             }
    
26.         }
    
27.         return dp[len][k];
    
28.     }
    
29. };

复制代码

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

糖逗

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