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

# bacabbb -> [b, aca, bbb] / [bacab, bb] => 1

# can we try dp? 

# b a c a b b b
# 0 1 2 1 0 1 1

# lemma: in the minimum cut, each letter will be in the longest palindrome it's possibly in 

# this is actually wrong, because 3rd b in the above case violate

# instead, we need to adjust: 

# in the minimum cut, 

# each letter will be in the longest palindrome it's possibly in after all its precessors meet the condition 

# With that we can try to put the letters in the right palindrom to achieve the problem with a greedy solution.


# how can we know whether a letter can be put in the palidrome
# so if we maintain an new array to mark where is the last letter's palindrom start, we can check to see 
# if the current letter can add to it

# brute force: try all the cut combination, there are n-1 possible cut and 
# combination is 2^(n-1), each combination takes up to O(n^2) to check palindrom


# another example violates the lemma we propose

# aaa b a 
# aa aba

# in this case  b is needed

# s can be up to 2000 length, we need to solve it with O(n^2) time


# bcktracking： 
# T(n) = T(n-1) + T(n-2) + ... + T(1) + n T(n-1) + T(n-2) + ... + T(1)
# to calculate, we will use 错位相减法
# T(n-1) = T(n-2) + ... + T(1) + n-1

# T(n) - T(n-1) = T(n-1) + 1
# T(n) = 2T(n-1) + 1 = O(2^n) + O(n)


class Solution:
    @functools.lru_cache(maxsize=1000*1000)
    def isPalindrome(self, s, i, j):
        if i > j:
            return True
        if (s[i] == s[j]):
            return self.isPalindrome(s, i+1, j-1)
        return False
    def minCut(self, s: str) -> int:
        n = len(s)
        # return minCut of s[st:]
        @functools.lru_cache(maxsize=1000*1000)
        def backtrack(s, st):
            res = len(s)-st-1 # abcde[2:] = cde
            for i in range(st, n):
                if self.isPalindrome(s, st, i):
                    res = min(res, 1+backtrack(s, i+1))
            # print(s[st:], res)
            return res
        return backtrack(s, 0)
    
            
        
        
354075