<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 {
    int n;
    vector<vector<bool>> palin;
    vector<vector<int>> dp;

    bool isPalindrome(string &s, int i, int j){
        while(i < j) if(s[i++] != s[j--]) return 0;
        return 1;
    }

    void fill_palin(string &s){
        for(int i = 0; i < n; i++) palin[i][i] = 1;
        for(int i = n-1; i >= 0; i--){
            for(int j = i+1; j < n; j++){
                if(i == j-1) palin[i][j] = (s[i] == s[j]);
                else if(s[i] == s[j]){
                    palin[i][j] = palin[i+1][j-1];
                }
            }
        }
    }
    int fun(string &s, int i, int j){
        // base case: can make palindrome of len 1 string in 0 cuts
        if(i >= j || palin[i][j]) return 0;
        if(dp[i][j] != -1) return dp[i][j];

        int cuts = INT_MAX;
        for(int k = i; k < j; k++){
            if(palin[i][k]){
                cuts = min(cuts, fun(s, k+1, j)+1);
            }
        }
        return dp[i][j] = cuts;
    }
    int fun_2(string &s, int i, int j){
        // base case: can make palindrome of len 1 string in 0 cuts
        if(i >= j || isPalindrome(s, i, j)) return 0;
        if(dp[i][j] != -1) return dp[i][j];

        int cuts = INT_MAX;
        for(int k = i; k < j; k++){
            if(isPalindrome(s, i, k)){
                cuts = min(cuts, fun_2(s, k+1, j)+1);
            }
        }
        return dp[i][j] = cuts;
    }

    int f(string &s, int i, int j){
        if(i >= j || palin[i][j]) return 0;
        if(dp[i][j] != -1) return dp[i][j];

        int ans = INT_MAX;
        for(int k = i; k <= j-1; k++){
            ans = min(ans, f(s, i, k) + f(s, k+1, j) + 1);
        }
        return dp[i][j] = ans;
    }    
    int f2(string &s, int i, int j){
        if(i >= j || isPalindrome(s, i, j)) return 0;
        if(dp[i][j] != -1) return dp[i][j];

        int ans = INT_MAX;
        for(int k = i; k <= j-1; k++){
            ans = min(ans, f2(s, i, k) + f2(s, k+1, j) + 1);
        }
        return dp[i][j] = ans;
    }    
public:
    int minCut(string s) {
        n = s.size();
        palin.resize(n, vector<bool>(n, 0));
        dp.resize(n, vector<int>(n, -1));

        /*
        // approach 1
        fill_palin(s);
        return fun(s, 0, s.size()-1);
        */
        
        /*
        // approach 2
        fill_palin(s);
        return f(s, 0, s.size()-1);
        */

        // apprach 1 without fill_palin
        return fun_2(s, 0, s.size()-1);
    }
};
65389