最小回文分割

题目描述
给出一个字符串s，分割s使得分割出的每一个子串都是回文串
计算将字符串s分割成回文分割结果的最小切割数
例如:给定字符串s="aab",
返回1，因为回文分割结果["aa","b"]是切割一次生成的。
示例1
输入
复制
"aab"
返回值
复制
1

class Solution {
public:
    /**
     * 
     * @param s string字符串 
     * @return int整型
     */
    int minCut(string s) {
        int n = s.size();
        if (n<=1) return 0;
       
        int dp[n+1];
        memset(dp,0x3f,sizeof dp);
        dp[0]=-1;
        for(int i=0;i<n;++i) {
            for(int len=0;i-len>=0 && i+len<n && s[i-len]==s[i+len];++len) {
                dp[i+len+1] = min(dp[i+len+1],dp[i-len]+1);
            }
            for(int len=0;i-len>=0 && i+len+1<n&& s[i-len]==s[i+len+1]; ++len) {
                dp[i+len+2] = min(dp[i+len+2],dp[i-len]+1);
            }
        }
        return dp[n];
    }
    bool isPalid(string &s,int i,int j) {
        while(i<j) if(s[i++]!=s[j--]) return false;
        return true;
    }
};

最小回文分割

原文：https://www.cnblogs.com/lyr-2000/p/14324592.html