<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:
    def minCut(self, s: str) -> int:
        # solution_dict = {}
        solution_dict = [False]*(len(s)+1)
        palindrome_dict = [[False]*(len(s)+1) for _ in range(len(s)+1)] #{}
        # print('yo')

        for i in range(len(s)):
        #     palindrome_dict[(i,i+1)] = True
        #     palindrome_dict[(i,i)] = True
            palindrome_dict[i][i+1] = True
            palindrome_dict[i][i] = True
        
        # # for i in range(len(s)-1):
        # #     palindrome_dict[(i,i+2)] = (s[i] == s[i+1])
        
        for length in range(2, len(s)+1):
            for i in range(len(s) - length+1):
                j = i + length 
                # palindrome_dict[(i, j)] = (s[i] == s[j-1] and palindrome_dict[(i+1, j-1)])
                palindrome_dict[i][j] = (s[i] == s[j-1] and palindrome_dict[i+1][j-1]) 


        # print(palindrome_dict)
        # print('ok')

        
        def check_palindrome(text):
            if text[::-1] == text:
                return True
            else:
                return False
        def find_solution(start, end, text):
            # if (start, end) in solution_dict:
            if solution_dict[end]:
                return solution_dict[end]
                # return solution_dict[(start, end)]
            # elif check_palindrome(text[start:end]):
            # elif palindrome_dict[(start, end)]:
            elif palindrome_dict[start][end]:

                # solution_dict[(start, end)] = 0
                solution_dict[end]= 0
                return 0
            else:
                min_cut = 10**5
                for i in range(start+1, end):
                    # if check_palindrome(text[i:end]):
                    if palindrome_dict[i][end]: #[(i, end)]:
                        curr_min = find_solution(start, i, text) + 1
                        min_cut = min(min_cut, curr_min)

                    # min_cut = min(min_cut, find_solution(start, i, text) + find_solution(i, end, text)+1)
                # solution_dict[(start, end)] = min_cut
                solution_dict[end] = min_cut
                return min_cut

        return find_solution(0, len(s), s)



60654