【LeetCode】132. 分割回文串 II_字符串 s,请你将 s 分割成一些子串,使每个子串都是回文串

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

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

示例:

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

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

https://www.bilibili.com/video/av78461289

看了B站这道题的教程才开始做的在这道题

作者讲的挺好，但是我好想也没听懂~~~

但是这个代码读懂了

先读懂这个代码，日后在研究这个思路吧~~~~·

现在我的能力还是比较弱。

第一层是遍历 回文串中间的值，然后通过 i和j在两边进行扩展。

d是判断奇数和偶数两种情况~

i>=0&&j<=n&&s[i]==s[j]循环条件

 dp[j]=min(dp[j],(i?(dp[i-1]+1):0));更新dp值

class Solution {
public:
    int minCut(string s) {
        const int n = s.length();
        vector<int> dp(n,n);
        for(int m=0;m<n;++m){
            for(int d=0;d<=1;d++){
                for(int i= m ,j=m+d;i>=0&&j<=n&&s[i]==s[j];--i,++j){
                    dp[j]=min(dp[j],(i?(dp[i-1]+1):0));
                }
            }
        }
        return dp[n-1];
    }
};