LeetCode-132-字符串-最少回文分割

从小到大的动态规划

//参考题目：https://leetcode-cn.com/problems/M99OJA/
class Solution {
public:
    int minCut(string s) {
        //方法一：借鉴 剑指 Offer II 086. 分割回文子字符串，https://leetcode-cn.com/problems/M99OJA/ 超时
        // vector path;
        // int min = INT_MAX;
        // dfs(s,0,path,min);
        // return min-1;

        //方法二，https://leetcode-cn.com/problems/palindrome-partitioning-ii/solution/fen-ge-hui-wen-chuan-ii-by-leetcode-solu-norx/
        // https://leetcode-cn.com/problems/palindrome-partitioning-ii/solution/wei-rao-li-lun-yu-chu-li-dong-tai-gui-hu-akpu/
        
        int n = s.size();
        //使用了备忘录记录回文字符串的信息，防止重复计算0
        vector> Palindrometable(n, vector(n, true));
        
        //Palindrometable[i][j]表示 s[i..j] 是否为回文串
        for (int i = n - 1; i >= 0; --i) 
        {
            for (int j = i + 1; j < n; ++j) 
            {   //从两边到中间来判断是否是回文
                Palindrometable[i][j] = (s[i] == s[j]) && Palindrometable[i+1][j-1];
            }
        }

        vector dp(n, INT_MAX);
        for (int i = 0; i < n; ++i) 
        {
            //字符串s[0][i]本来就是回文字符串，不需要分割，故 dp[i] = 0
            if (Palindrometable[0][i]) 
            {
                dp[i] = 0;
            }
            else 
            {   // 0<=j& path, int& min)
    {
        if (begin == str.size())
        {
            min = min > path.size() ? path.size() : min;
            return;
        }

        for (int end=begin;end end)
        {
            return false;
        }

        while (begin < end)
        {
            if (str[begin++] != str[end--])
            {
                return false;
            }
        }

        return true;
    }    
};