132. 分割回文串 II

给你一个字符串 s，请你将 s 分割成一些子串，使每个子串都是回文。

返回符合要求的 最少分割次数 。

 

示例 1：

输入：s = "aab"
输出：1
解释：只需一次分割就可将 s 分割成 ["aa","b"] 这样两个回文子串。

> 动态规划

class Solution {
public:
    int minCut(string s) {
        vector<vector<int>> dp(s.size(),vector<int>(s.size(),1));
        for(int i = s.size()-1;i >= 0;i--){
            for(int j = s.size()-1;j > i;j--){
                if(s[i] == s[j]){
                    dp[i][j] = dp[i+1][j-1];
                }
                else{
                    dp[i][j] = 0;
                }
            }
        }
        int n = s.size();
        vector<int> f(n);
        for(int j = 1; j < n; j++) {
            if(dp[0][j])
                f[j] = 0;
            else {
                f[j] = f[j-1] + 1;
                for(int i = 1; i < j; i++) {
                    if(dp[i][j])
                        f[j] = min(f[j], f[i-1] + 1);
                }
            }
        }
        return f[n-1];
    }
};