1、思路

• 先对字符串进行预处理，isPal[j][i]表示从字符s[j]到s[i]的子串是否回文，预处理分两种情况：
  1、若子串字符在两个以内且俩字符相等，则该子串回文；
  2、若子串的头尾两个字符相等，且中间部分回文，则该子串回文；

• 预处理完毕后，开始DP，dp[i]表示从字符串开头到第i个字符的最少回文分割次数，需要两重循环：
  1、第一重循环：判断s[0 ~ i]子串本身是否为回文子串，若是，则最少分割次数为0；
  2、第二重循环：计算状态转移方程，若s[j ~ i]是回文，则只需要在s[j - 1]和s[j]之间再做一次分割即可，即dp[i]为所有符合条件的j对应的dp[j - 1]的最小值加1。

2、代码

class Solution {
public:
    int minCut(string s) {
        int len = s.length();
        vector<vector<bool>> isPal(len, vector<bool>(len));

        for (int i = 0; i < len; ++ i)
        {
            for (int j = 0; j <= i; j ++ )
            {
                char ch1 = s[i], ch2 = s[j];
                //i <= j + 1 表示从s[j]到s[i]在两个字符以内
                if (ch1 == ch2 && (i <= j + 1 || isPal[j + 1][i - 1]))  
                {
                    isPal[j][i] = true;
                }
            }
        }

        vector<int> dp(len);
        for (int i = 0; i < len; ++ i)
        {
            if (isPal[0][i])
            {
                dp[i] = 0;      // s[0 ~ i] 本身就是回文子串，最少回文分割为 0
            }
            else
            {
                dp[i] = i;      // s[0 ~ i] 的最大回文分割次数为 i
                for (int j = 1; j <= i; ++ j)
                {
                    if (isPal[j][i])    //若 s[j ~ i]为回文
                    {                   //只需要在s[j - 1]和s[j]之间再做一次分割即可
                        dp[i] = min(dp[i], dp[j - 1] + 1);
                    }
                }
            }
        }

        return dp[len - 1];
    }
};