132. Palindrome Partitioning II

132.cpp

class Solution {
public:
    int minCut(string s) {
        unsigned long t = s.size();
        vector<vector<bool>> p(t, vector<bool>(t, false));
        vector<int> dp(t, INT_MAX);
        for (int i = 0; i < t; ++i) {
            for (int j = i; j >= 0; --j) {
                if ((i - j <= 1 || p[j + 1][i - 1]) && s[i] == s[j]) {
                    p[j][i] = true;
                }
                if (p[j][i]) {
                    if (j == 0) {
                        dp[i] = 0;
                    } else {
                        dp[i] = min(dp[i], dp[j - 1] + 1);
                    }
                }
            }
        }

        return dp[t - 1];
    }
};