Palindrome Partitioning II

# top-down memo
class Solution:
    def minCut(self, s: str) -> int:
        memo_mincut = dict()
        memo_palindrome = dict()
        
        def is_palindrome(start, end):
            if (start, end) in memo_palindrome:
                return memo_palindrome[(start, end)]
            
            if start >= end:
                return True
            
            memo_palindrome[(start, end)] = (is_palindrome(start + 1, end - 1) and s[start] == s[end])
            return memo_palindrome[(start, end)]
        
        def dfs(idx):
            if is_palindrome(idx, len(s) - 1):
                return 0
            
            if idx in memo_mincut:
                return memo_mincut[idx]
            
            ans = math.inf
            for i in range(idx, len(s)):
                if is_palindrome(idx, i):
                    ans = min(ans, dfs(i + 1) + 1)
            
            memo_mincut[idx] = ans
            return ans

        return dfs(0)

# bottom-up DP
class Solution:
    def minCut(self, s: str) -> int:
        N = len(s)
        dp = [math.inf] * (N + 1)
        dp[0] = -1

        memo_palindrome = dict()

        def is_palindrome(start, end):
            if (start, end) in memo_palindrome:
                return memo_palindrome[(start, end)]

            if start >= end:
                return True
            
            memo_palindrome[(start, end)] = is_palindrome(start + 1, end - 1) and s[start - 1] == s[end - 1]
            return memo_palindrome[(start, end)]
        
        for i in range(1, N + 1):
            for j in range(i, 0, -1):
                if is_palindrome(j, i):
                    dp[i] = min(dp[i], dp[j - 1] + 1)
        
        return dp[N]

# two-pointer optimised (i.e. expand from centre)
class Solution:
    def minCut(self, s: str) -> int:
        N = len(s)
        dp = [math.inf] * N

        def optimal_sub_problem(left, right, dp):
            while 0 <= left  and  right < len(s) and s[left] == s[right]:
                if left == 0:
                    dp[right] = 0

                dp[right] = min(dp[right], dp[left - 1] + 1)
                left -= 1
                right += 1
        
        for i in range(N):
            optimal_sub_problem(i, i, dp)
            optimal_sub_problem(i - 1, i, dp)

        return dp[N - 1]