class Solution {
public:
    int isPallindrome(string a) {

        int e = a.length()-1;
        int s=0;
        while(s<=e) {
            if(a[s]==a[e]) { s++; e--; } else { return false;}
        }
        return true;
    }
    int f(int i,int j,string s,vector<vector<int>> &dp) {

      if(i>=j) {  return 0; }
      if(isPallindrome(s))   { return 0; }

      if(dp[i][j]!=-1) return dp[i][j];

        int minI = INT_MAX;

        for(int k=i;k<j;k++) {
            int pCount = 1 + f(i,k,s,dp) + f(k+1,j,s,dp);
            minI = min(pCount,minI);
             // cout<<"mini:"<<minI<<endl;
        }

        return  dp[i][j]=minI;
        //Only 1 char-> is pallindrome}
    }
    int minCut(string s) {
        vector<vector<int>> dp(s.length()+1,vector<int>(s.length()+1,-1));
      return f(0,s.length()-1,s,dp);
    }
};