C++刷LeetCode（132. 分割回文串 II）【动态规划】

糖逗

题目描述：

1. 给定一个字符串 s，将 s 分割成一些子串，使每个子串都是回文串。
   
2. 
   
3. 返回符合要求的最少分割次数。
   
4. 
   
5. 示例:
   
6. 
   
7. 输入: "aab"
   
8. 输出: 1
   
9. 解释: 进行一次分割就可将 s 分割成 ["aa","b"] 这样两个回文子串。

复制代码

1. class Solution {
   
2. public:
   
3.     bool valid(string & s, int i , int j){//验证是回文
   
4.         int left = i, right = j;
   
5.         while(left < right){
   
6.             if(s[left] != s[right])return false;
   
7.             left++;
   
8.             right--;
   
9.         }
   
10.         return true;
    
11.     }
    
12.     int minCut(string s) {
    
13.         int len = s.size();
    
14.         if (len < 2)return 0;
    
15.         vector<int> dp(len, 0);
    
16.         for(int i = 0; i < len; i++)dp[i] = i;
    
17.         for(int i = 1; i < len ;i++){
    
18.             if (valid(s, 0, i)){
    
19.                 dp[i] = 0;
    
20.                 continue;
    
21.             }
    
22.             for(int j = 0; j <= i; j++){
    
23.                 if(valid(s, j + 1, i)){
    
24.                     dp[i] = min(dp[i], dp[j] + 1);
    
25.                 }
    
26.             }
    
27.         }
    
28.         return dp[len - 1];
    
29.     }
    
30. };

复制代码

参考链接：https://leetcode-cn.com/problems ... -by-liweiwei1419-2/