# https://leetcode.com/problems/palindrome-partitioning-ii/submissions/
# yes, can memoize both cut() & isPal()
class Solution:
    def minCut(self, s: str) -> int:
        pal_memo = [[None for _ in range(len(s))] for _ in range(len(s))]
        cut_memo = [[None for _ in range(len(s))] for _ in range(len(s))]
        def isPal(start, end, memo):
            if start >= end:
                return True

            if memo[start][end] != None:
                return memo[start][end]
            else:
                res = (s[start] == s[end]) and isPal(start+1, end-1, memo)
                memo[start][end] = res
                return res
        
        def cut(start, end, memo):
            if start == end or isPal(start, end, pal_memo): # this is impt!! prune the recursive tree
                return 0
            
            if memo[start][end] != None:
                return memo[start][end]
            else:
                res = len(s)-1
                for i in range(start, end):
                    if isPal(start, i, pal_memo):
                        res = min(res, 1 + cut(i+1, end, memo))
                memo[start][end] = res
                return res
        
        return cut(0, len(s)-1, cut_memo)

class Solution_memo_dict:
    # LESSONS LEARNT: dont put memo_p as argument in cut --> greatly slows it down
    # using array for memo often saves time & memory than dict
    # define memo at the top before defining helper functions
    def minCut(self, s: str) -> int:
        memo_p = {}
        def isPalin(l, r, memo):
            if l >= r:
                return True
            
            if (l, r) in memo:
                return memo[(l, r)]
            else:
                if (s[l] == s[r]) and isPalin(l+1, r-1, memo):
                    res = True
                else:
                    res = False
                memo[(l, r)] = res
                return res
    
        def cut(l, r, memo_c):
            if l == r or isPalin(l, r, memo_p):
                return 0
            
            if (l, r) in memo_c:
                return memo_c[(l, r)]
            else:
                res = float('+inf')
                for j in range(l, r):
                # for j in range(r-1, l-1, -1):
                    if isPalin(l, j, memo_p):
                        res = min(res, 1 + cut(j+1, r, memo_c))
                    
                memo_c[(l, r)] = res
                return res
        
        return cut(0, len(s)-1, {})