My Approach:

Create a bool 2D vector to capture the palindrome at index i with a length len.

I start doing this from the rear end of the string. When calculating, I update minCuts required at each index

Case I: As and when i can reach end from this index directly when forming a palindrome

Case II: I form a palindrome from curr index and reach another index and use its minCut value to get the minCut value of current index. Update this value across all possible palindromes from curr index.

```
class Solution {
public:
int minCut(string s) {
int n = s.size();
vector<vector<bool> > bpal(n+1, vector<bool>(n+1,0));
vector<int> minCut(n,INT_MAX);
minCut[n-1] = 0;
for(int i=n-2;i>=0;i--)
{
for(int len=1;len<n+1-i;len++)
{
if(s[i] ==s[i+len-1] and (len<=2 or bpal[i+1][len-2]))
{
bpal[i][len] = true;
if(i+len==n)
minCut[i] = 0;
else if(i+len<n and minCut[i+len] !=INT_MAX)
minCut[i] = min(minCut[i+len]+1, minCut[i]);
}
}
}
return minCut[0];
}
};
```