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

/*
itself is palindrome, easy

we must find some t such that [0,t] is, and deal with the rest, and we want to maximise t (recur);
naive: from end call check palindrom one by one (probably not that bad, O(n^2))

reuseable sub_structure? 
[0,t] => [1,t-1] not very useful

memorised dp?

*/
class Solution {
public:
    int minCut(string s) {
        bool isp[s.size()][s.size()];
        for(int d=0;d<s.size();d++) {
            for(int i = 0; i+d < s.size();i++) {
                if(d == 0) {
                    isp[i][i] = true;
                } else if(d == 1) {
                    isp[i][i+1] = s[i] == s[i+1];
                } else {
                    isp[i][i+d] = s[i] == s[i+d] && isp[i+1][i+d-1];
                }
            }
        }

        int dp[s.size()][s.size()];
        memset(dp,-1,sizeof(dp));
        function<int(int,int)> f = [&dp,s,&isp,&f](int left, int right) {
            //cout <<left <<" " <<right <<"\n";
            if(dp[left][right] >= 0) {
                return dp[left][right];
            }
            dp[left][right] = s.size() + 1;
            if (isp[left][right]) {
                dp[left][right] = 0;
            } else {
                for(int i=left;i<right;i++) {
                    if(isp[left][i]) {
                        dp[left][right] = min(dp[left][right],f(left,i) + f(i+1,right) + 1);
                    }
                }
            }
            return dp[left][right];
        };
        f(0,s.size()-1);
        /*
        for(int i=0;i<s.size();i++) {
            for(int j=0;j<s.size();j++) {
                cout << cache[i][j] << " ";
            }
            cout <<"\n";
        }
        cout <<"\n";
        for(int i=0;i<s.size();i++) {
            for(int j=0;j<s.size();j++) {
                cout << dp[i][j] << " ";
            }
            cout <<"\n";
        }
        */
        return f(0,s.size()-1);
    }
    
};
31395