Palindrome Partitioning II [Leetcode]

Given a string s, partition s such that every substring of the partition is a palindrome.
Return the minimum cuts needed for a palindrome partitioning of s.
For example, given s = "aab",
Return 1 since the palindrome partitioning ["aa","b"] could be produced using 1 cut.

Solution: of course we will get TLE using backtracking here. Basically, it is always good to give DP a shot to solve optimization problem [other good solutions or explanations: 1, 2, 3, 4]

class Solution {
public:
    int minCut(string s) {
        // Note: The Solution object is instantiated only once and is reused by each test case.
        if(s.empty()) return 0;
        
        int n = s.size();
        vector<vector<bool> > isP(n, vector<bool>(n, false));
        vector<int> minC(n, INT_MAX);
        
        //computer all palindromes
        for(int i=n-1; i>=0; i--)
            for(int j=i; j<n; j++){
                if(s[i]==s[j] && (j-i<2 || isP[i+1][j-1]))
                    isP[i][j]=true;
                else
                    isP[i][j]=false;
            }
        
        //DP
        //minC[i] = 0 if s[0,..., i] is palindrome
        //        = min(minC[j]+1) for all 0<=j<i && s[j+1,..., i] is palindrome
        for(int i=0; i<n; i++){
            int minI = INT_MAX;
            if(isP[0][i]){
                minC[i] = 0;
                continue;
            }
            for(int j=0; j<i; j++){
                if(isP[j+1][i])
                    minI = min(minI, minC[j]+1);
            }
            minC[i] = minI;
        }
        
        return minC[n-1];
    }
};