题解 | #分割回文串-ii#

// 状态：F(i)前i个字符的最小切割数
// 转移方程：如果当前整体是回文串：F(i)=0
//          整体不是：F(i)=min(F(j)+1)
//                  前提：j<i并且[j+1,i]是回文串
// 初始值：F(i)=i-1(最大分割数：字符个数-1)
// 返回结果：F(s.size())
#include <string>
class Solution {
public:
    /**
     * 
     * @param s string字符串 
     * @return int整型
     */
    //判断回文
    bool ispal(string& s,int left,int right)
    {
        string str=s.substr(left,right-left+1);
        string rstr=str;
        reverse(str.begin(),str.end());
        if(str==rstr)
            return true;
        return false;
    }
    int minCut(string s) {
        int len=s.size();
        //判断字符串整体是否回文
        if(ispal(s,0,len-1))
        {
            return 0;
        }

        vector<int> arr(len+1);
        //初始状态
        for(int i=1;i<=len;i++)
        {
            arr[i]=i-1;
        }
        for(int i=2;i<=len;i++)
        {
            if(ispal(s,0,i-1))
                arr[i]=0;
            else
            {
                for(int j=i-1;j>0;j--)
                {
                    if(ispal(s,j,i-1)&&((arr[j]+1)<arr[i]))
                    {
                        arr[i]=arr[j]+1;
                    }
                }
            }
        }
        return arr[len];
    }
};