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

糖逗

题目描述：

给定一个字符串 s，将 s 分割成一些子串，使每个子串都是回文串。

返回符合要求的最少分割次数。

示例:

输入: "aab"
输出: 1
解释: 进行一次分割就可将 s 分割成 ["aa","b"] 这样两个回文子串。

class Solution {
public:
    bool valid(string & s, int i , int j){//验证是回文
        int left = i, right = j;
        while(left < right){
            if(s[left] != s[right])return false;
            left++;
            right--;
        }
        return true;
    }
    int minCut(string s) {
        int len = s.size();
        if (len < 2)return 0;
        vector<int> dp(len, 0);
        for(int i = 0; i < len; i++)dp[i] = i;
        for(int i = 1; i < len ;i++){
            if (valid(s, 0, i)){
                dp[i] = 0;
                continue;
            }
            for(int j = 0; j <= i; j++){
                if(valid(s, j + 1, i)){
                    dp[i] = min(dp[i], dp[j] + 1);
                }
            } 
        }
        return dp[len - 1];
    }
};

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