<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>

class Solution {
public:
    bool isPalindrome(string s,int i,int j,vector<vector<int>> &palindrome){
        if (i >= j) return palindrome[i][j]=true;
        if (palindrome[i][j] != -1) return palindrome[i][j];
        if (s[i] == s[j]) return palindrome[i][j] = isPalindrome(s, i + 1, j - 1,palindrome);
        return palindrome[i][j] = false;
    }
    int solve(string s,int index,vector<int>&dp,vector<vector<int>> &palindrome){
        if(index>=s.size()) return 0;

        int mini = 1e4;
        if(dp[index]!=-1) return dp[index];
        for(int i=index;i<s.size();i++){
            if(isPalindrome(s,index,i,palindrome)){
                mini = min(mini,1 + solve(s,i+1,dp,palindrome));
            } 
        }
        return dp[index] = mini;
    }
    int minCut(string s) {
        vector<vector<int>> palindrome(s.size()+1,vector<int>(s.size()+1,-1));
        // vector<int>dp1(s.size()+1,-1);
        // return solve(s,0,dp1,palindrome) -1;
        vector<vector<bool>> palindromeArray(s.size()+1,vector<bool>(s.size()+1,false));
        int n = s.size();
        vector<int>dp(s.size()+1,0);
        for (int i = n - 1; i >= 0; i--) {
            for (int j = i; j < n; j++) {
                if (s[i] == s[j] && (j - i <= 2 || palindromeArray[i + 1][j - 1])) {
                    palindromeArray[i][j] = true;
                }
            }
        }

        for(int index=s.size()-1;index>=0;index--){
            int mini = 1e4;
            for(int i=index;i<s.size();i++){
                if(palindromeArray[index][i]){
                    mini = min(mini,1 + dp[i+1]);
                } 
            }
            dp[index] = mini;
        }
        return dp[0]-1;
    }
};
65389