Description

Submission

class Solution {
    int dp[2001][2001];
    
    int n;
public:
    int minCut(string s) {
        n = s.size();

        for(int i = 0; i < n; ++i) {
            dp[i][i] = 1;
        }

        for(int i = 1; i < n; ++i) {
            if(s[i] == s[i-1]) dp[i-1][i] = 1;
        }

        for(int len = 3; len <= n; ++len) {
            for(int i = 0; i+len-1 < n; ++i) {
                int j = i+len-1;
                if(s[i] == s[j]) dp[i][j] = dp[i+1][j-1];
            }
        }
        vector<int> shortest(n, INT_MAX/2);
        for(int i = 0; i < n; ++i) {
            if(dp[0][i]) {
                shortest[i] = 0;
            } else {
                for(int j = i; j >= 0; --j) {
                    if(dp[j][i])
                        shortest[i] = min(shortest[i], shortest[j-1] + 1);
                }
            }
        }

        return shortest[n-1];
    }

    
};