回文字符串ii（最少切割次数）

典型的动态规划问题：

1. 对于每个位置i，以递增的方式找长度为1,3,5,7...的回文子串，然后找长度为2,4,6,8的回文子串；
2. 假设回文子串的起始位置为idx_s，结束位置为idx_e，更新dp数组的公式为dp[idx_e] = min(dp[idx_s-1] + 1, dp[idx_e])
3. 考虑到idx_s=0的情况，我们将dp[0]置为-1

代码如下：

//
// Created by jt on 2020/8/23.
//
#include <vector>
#include <string>
using namespace std;

class Solution {
public:
    /**
     *
     * @param s string字符串
     * @return int整型
     */
    int minCut(string s) {
        // write code here
        // dp[0] = 0, dp[1] = 0, dp[i] = min(dp[j] + 1, dp[j]) 其中0<=j<i
        int sz = s.size();
        vector<int> dp(sz+1, INT_MAX);
        dp[0] = -1;
        for (int i = 0; i < sz; ++i) {
            // 回文长度为1, 3, 5, 7, 9...
            for (int len = 0; i - len >= 0 && i + len < sz && s[i-len] == s[i+len]; len++) {
                dp[i+len+1] = min(dp[i+len+1], dp[i-len] + 1);
            }

            // 回文长度为2, 4, 6, 8, 10...
            for (int len = 0; i - len >= 0 && i + len + 1 < sz && s[i-len] == s[i+len+1]; len++) {
                dp[i+len+2] = min(dp[i+len+2], dp[i-len] + 1);
            }
        }
        return dp[sz];
    }
};