class Solution {
public:
    int minCut(string s) {

        int n = (int)s.size();
        vector<vector<bool>>palin(n+1, vector<bool>(n+1,false));

        //palin(i, j) the substring i...j is palindrome or not.
        vector<int>dp(n+1, 0); // minimum cut for the 0...ith char.

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

        for(int i=2;i<=n;i++){
            for(int j=i-1;j>=0;j--){

                if(s[i-1] == s[j]  && (i-1-j<2 || palin[j+1][i-1])){
                    palin[j][i] = true;

                    dp[i] = min(dp[i], dp[j]+1);
                }
            }
        }



        return dp[n];

    }


};

// space can be optimized, just use the even, odd palindrome concept.