LeetCode 132. 分割回文串 II

LeetCode 132. 分割回文串 II
思路：

代码：

class Solution {
public:
    int minCut(string s) {
        int n = s.size();
        s = ' ' + s;
        vector<int> f(n + 1,1e8);
        vector<vector<bool>> g(n+1,vector<bool> (n + 1));

        for(int j=1;j<=n;j++){
            for(int i=1;i<=j;i++){
                if(i == j) g[i][j] = true;
                else if(s[i] == s[j]){
                    if(i + 1 > j - 1 || g[i+1][j-1]) g[i][j] = true;
                }
            }
        }

        f[0] = 0;
        for(int i = 1;i <= n;i++){
            for(int j = 1;j <= i ;j++){
                if(g[j][i]){
                    f[i] = min(f[i],f[j-1] + 1);
                }
            } 
        }

        return f[n] - 1;
    }
};