https://leetcode.com/problems/palindrome-partitioning-ii/discussion/

class Solution {
public:
    int isPallindrome(string a,int i,int j) {

        int e = j;
        int s=i;
        while(s<=e) {
            if(a[s]==a[e]) { s++; e--; } else { return false;}
        }
        return true;
    }




    int f(int i,string s,vector<int> &dp) {

        //Using memoization;
   if(i>=s.length()) return 0;
   if(dp[i]!=-1) return dp[i];
   int minC = 1e9;
   bool ran=false;
   for(int k=i;k<s.length();k++) {
       if(isPallindrome(s,i,k)) {
           ran=true;
           int count = 1 + f(k+1,s,dp);
           minC = min(minC,count);

       }
   }
   return  dp[i] = (!ran)?0:minC;
    }




    int minCut(string s) {
//vector<int> dp(s.length()+1,-1);
     //   return f(0,s,dp)-1;


        vector<int> dp(s.length()+1,0);

        for(int i=s.length()-1;i>=0;i--) {
int minC = 1e9;
   bool ran=false;
   for(int k=i;k<s.length();k++) {
       if(isPallindrome(s,i,k)) {
           ran=true;
           int count = 1 + dp[k+1];
           minC = min(minC,count);

       }
   }
   dp[i]= (!ran)?0:minC;

        }
      return dp[0]-1;
    }
};