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

auto speedUp = []() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);
    return 0;
}();

class Solution {
public:
    int minCut(string &s) {
        int n = s.size();
        int memo[n][n];
        memset(memo, -1, sizeof(memo));
        for(int i = 0; i < n; i++) {
            int l, r;
            l = i;
            r = i;
            while(0 <= l and r < n) {
                if(s[l] != s[r]) break;
                memo[l][r] = 0;
                l--;
                r++;
            }
            l = i;
            r = i + 1;
            while(0 <= l and r < n) {
                if(s[l] != s[r]) break;
                memo[l][r] = 0;
                l--;
                r++;
            }
        }
        int r = n - 1;
        function<int(int)> dp;
        dp = [&](int l) {
            if(memo[l][r] == -1) {
                memo[l][r] = INT_MAX / 2;
                for(int mid = l; mid < r; mid++) {
                    if(memo[l][mid] == 0)
                        memo[l][r] = min(memo[l][r], 1 + dp(mid + 1));
                }
            }
            return memo[l][r];
        };
        return dp(0);

    }
};
26539