# 92 ms c++ DP solution. Please suggest me where i can improve

• 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];
}
};``````

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.