class Solution {

public:
    int minCut(string s) {

        int n=s.length();
        vector<vector<int>> dp(n,vector<int> (n,-1));
        dp[0][n-1]=PalPartition(0,n-1,s,dp);

        return dp[0][n-1];
    }
    int PalPartition(int i,int j,string s,vector<vector<int>> &dp){

        //base case
        if(i>j)     return 0;
        if(dp[i][j] != -1)  return dp[i][j];
        if(isPalindrome(s,i,j))     return 0;

        int cuts=INT_MAX-1,tempCut=0;
        for(int k=i;k<j;k++){
            tempCut=1+PalPartition(i,k,s,dp)+PalPartition(k+1,j,s,dp);
            cuts=min(cuts,tempCut);
        }
        dp[i][j]=cuts;
        return dp[i][j];
    }
    bool isPalindrome(string s,int i,int j){

        while(i<j){
            if(s[i] != s[j])
                return false;
            i++;j--;
        }
        return true;
    }
};