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

class Solution {
public:
    /**
     * 
     * @param s string字符串 
     * @return int整型
     */
    bool isPal(string &s,int start,int end)
    {
        while(start < end)
        {
            if(s[start] !=s[end])
            {
                return false;
            }
            start++;
            end--;
        }
        return true;
    }

    int minCut(string s) {
        // write code here
       //===========状态定义及初始化==================
        vector<int> F(s.size()+1);     // F[i] 表示前i个字符的最小分割数；
        for(int i = 1;i<=s.size(); ++i)
        {
            F[i] = i-1;   // i个字符 最大分割数为i-1;  
        }
        // ==============状态递推===================
        for(int i = 2; i<= s.size();++i)
        {
            // 判断整体
            if(isPal(s,0,i-1)) // 整体是回文
            {
                F[i] = 0; // 表示从头到第i个字符的最小分割数
            }
            else                // 整体不是回文
            {
                for(int j = 1; j < i ;j++)
                {
                    if(isPal(s, j, i-1)) // 相当于 图中“|”后面的字符串
                    {
                        F[i] = min(F[i], F[j] + 1);
                    }
                }
            }
        }
        return F[s.size()];
    }
};