<p>Given a string <code>s</code>, partition <code>s</code> such that every <span data-keyword="substring-nonempty">substring</span> of the partition is a <span data-keyword="palindrome-string">palindrome</span>.</p>

<p>Return <em>the <strong>minimum</strong> cuts needed for a palindrome partitioning of</em> <code>s</code>.</p>

<p>&nbsp;</p>
<p><strong class="example">Example 1:</strong></p>

<pre>
<strong>Input:</strong> s = &quot;aab&quot;
<strong>Output:</strong> 1
<strong>Explanation:</strong> The palindrome partitioning [&quot;aa&quot;,&quot;b&quot;] could be produced using 1 cut.
</pre>

<p><strong class="example">Example 2:</strong></p>

<pre>
<strong>Input:</strong> s = &quot;a&quot;
<strong>Output:</strong> 0
</pre>

<p><strong class="example">Example 3:</strong></p>

<pre>
<strong>Input:</strong> s = &quot;ab&quot;
<strong>Output:</strong> 1
</pre>

<p>&nbsp;</p>
<p><strong>Constraints:</strong></p>

<ul>
	<li><code>1 &lt;= s.length &lt;= 2000</code></li>
	<li><code>s</code> consists of lowercase English letters only.</li>
</ul>

#define pb push_back
#define mp make_pair
#define fi first
#define se second
#define ins insert
#define vii vector<int>
#define pii pair<int,int>
const int N = 2001;
vii dp(N,-1);
int n;

void initialize(){
    for(int i=0;i<=n;i++)
        dp[i] = -1;
}

bool isPalindrome(int startIndex,string& s){
    int l = startIndex;
    int r = s.size()-1;
    int isValid = true;
    while(l<=r){
        if(s[l]!=s[r]){
            isValid = false;
            break;
        }
        l++;
        r--;
    }
    return isValid;
}

int getMinimumCuts(int index,string& s){
    if(dp[index]!=-1)
        return dp[index];
        
    if(isPalindrome(index,s)){
        dp[index] = 0;
        return dp[index];
    }

    string temp = "";
    int finalAns = INT_MAX;
    for(int i=index;i<n;i++){
        temp += s[i];
        if(isPalindrome(0,temp)){
            if(dp[i+1]==-1)
                dp[i+1] = getMinimumCuts(i+1,s);
            int tempAns = 1+dp[i+1];
            finalAns = min(finalAns,tempAns);
        }
    }
    dp[index] = finalAns;
    return dp[index];
}

class Solution {
public:
    int minCut(string s) {
        n = s.size();
        initialize();
        dp[0] = getMinimumCuts(0,s);
        return dp[0];
    }
};
30424