def longestCommonSubsequence(text1: str, text2: str) -> int:
    memo = {}

    def dfs(i: int, j: int) -> int:
        if i == len(text1) or j == len(text2):
            return 0
        if (i, j) in memo:
            return memo[(i, j)]

        if text1[i] == text2[j]:
            memo[(i, j)] = 1 + dfs(i + 1, j + 1)
        else:
            memo[(i, j)] = max(dfs(i + 1, j), dfs(i, j + 1))
        return memo[(i, j)]

    return dfs(0, 0)

    def longestCommonSubsequence(text1: str, text2: str) -> int:
    memo = {}

    def dfs(i: int, j: int) -> int:
        if i == len(text1) or j == len(text2):
            return 0
        if (i, j) in memo:
            return memo[(i, j)]

        if text1[i] == text2[j]:
            memo[(i, j)] = 1 + dfs(i + 1, j + 1)
        else:
            memo[(i, j)] = max(dfs(i + 1, j), dfs(i, j + 1))
        return memo[(i, j)]

    return dfs(0, 0)

    def longestCommonSubsequence(text1: str, text2: str) -> int:
        m, n = len(text1), len(text2)
        dp = [[0] * (n + 1) for _ in range(m + 1)]

        for i in range(1, m + 1):
            for j in range(1, n + 1):
                if text1[i-1] == text2[j-1]:
                    dp[i][j] = 1 + dp[i-1][j-1]
                else:
                    dp[i][j] = max(dp[i-1][j], dp[i][j-1])

        return dp[m][n]

    def longestCommonSubsequence(text1: str, text2: str) -> int:
        m, n = len(text1), len(text2)
        prev = [0] * (n + 1)

        for i in range(1, m + 1):
            curr = [0] * (n + 1)
            for j in range(1, n + 1):
                if text1[i-1] == text2[j-1]:
                    curr[j] = 1 + prev[j-1]
                else:
                    curr[j] = max(prev[j], curr[j-1])
            prev = curr

        return prev[n]

    def uniquePaths(m, n):
        # dp[r][c] = number of ways to reach (r, c)
        dp = [[1]*n for _ in range(m)]
        for r in range(1, m):
            for c in range(1, n):
                dp[r][c] = dp[r-1][c] + dp[r][c-1]
        return dp[m-1][n-1]

    def knapsack(weights, values, capacity):
        n = len(weights)
        dp = [[0]*(capacity+1) for _ in range(n+1)]
        for i in range(1, n+1):
            for w in range(1, capacity+1):
                if weights[i-1] <= w:
                    dp[i][w] = max(dp[i-1][w], dp[i-1][w-weights[i-1]] + values[i-1])
                else:
                    dp[i][w] = dp[i-1][w]
        return dp[n][capacity]

    def matrixChain(p):
        n = len(p) - 1
        dp = [[0]*n for _ in range(n)]
        for length in range(2, n+1):
            for i in range(n-length+1):
                j = i + length - 1
                dp[i][j] = min(
                    dp[i][k] + dp[k+1][j] + p[i]*p[k+1]*p[j+1]
                    for k in range(i, j)
                )
        return dp[0][n-1]

    def lcs(text1, text2):
        m, n = len(text1), len(text2)
        dp = [[0]*(n+1) for _ in range(m+1)]
        for i in range(m-1, -1, -1):
            for j in range(n-1, -1, -1):
                if text1[i] == text2[j]:
                    dp[i][j] = 1 + dp[i+1][j+1]
                else:
                    dp[i][j] = max(dp[i+1][j], dp[i][j+1])
        return dp[0][0]

    def dfs(node):
        if not node: return (0, 0)
        leftRob, leftSkip = dfs(node.left)
        rightRob, rightSkip = dfs(node.right)

        rob = node.val + leftSkip + rightSkip
        skip = max(leftRob, leftSkip) + max(rightRob, rightSkip)
        return (rob, skip)

    robRoot, skipRoot = dfs(root)
    answer = max(robRoot, skipRoot)

    def dfs(node):
        if node in memo: return memo[node]
        best = 0
        for nei in graph[node]:
            best = max(best, 1 + dfs(nei))
        memo[node] = best
        return best

    answer = max(dfs(node) for node in all_nodes)

    def dp(mask, i):
        if mask == (1 << n) - 1:
            return 0
        if (mask, i) in memo: return memo[(mask, i)]

        best = float('inf')
        for j in range(n):
            if not (mask & (1 << j)):
                best = min(best, graph[i][j] + dp(mask | (1 << j), j))
        memo[(mask, i)] = best
        return best

    answer = min(dp(1 << i, i) for i in range(n))

    def uniquePaths(self, m: int, n: int) -> int:
        
        # Note:
        # Bottom Up Tabulation
        # 1. Initialize Array -> dp[i][j] = number of ways to reach cell (i,j)
        # 2. Base Set Up -> first row and first column = 1 (only one way)
        # 3. Explore -> fill dp for all cells from (1,1) to (m-1,n-1)
        # 4. Build -> dp[i][j] = dp[i-1][j] + dp[i][j-1]
        # Result: dp[m-1][n-1] = unique paths to bottom-right corner

        # Initialize Array -> m x n grid
        dp = [[0] * n for _ in range(m)]

        # Base Set Up -> first row and first col = 1
        for i in range(m):
            dp[i][0] = 1
        for j in range(n):
            dp[0][j] = 1

        # Process -> from (1,1) to (m-1,n-1)
        for i in range(1, m):
            for j in range(1, n):
                # Explore Choices -> from top or left
                top = dp[i-1][j]
                left = dp[i][j-1]

                # Build -> total ways
                dp[i][j] = top + left

        # Result -> bottom-right cell
        res = dp[m-1][n-1]

        # overall: time complexity O(m*n)
        # overall: space complexity O(m*n)
        return res

    def uniquePaths(self, m: int, n: int) -> int:
        
        # Note:
        # Bottom Up Variables (row compression)
        # 1. Initialize Row -> dp[j] = number of ways to reach column j in current row
        # 2. Base Set Up -> first row = all 1's
        # 3. Explore -> update row from left to right
        # 4. Build -> dp[j] = dp[j] + dp[j-1]
        # Result: dp[n-1] = unique paths to bottom-right corner

        # Initialize Row -> all 1's for first row
        dp = [1] * n

        # Process -> rows 1 to m-1
        for i in range(1, m):
            for j in range(1, n):
                # Explore + Build -> update in-place
                dp[j] = dp[j] + dp[j-1]

        # Result -> bottom-right cell
        res = dp[n-1]

        # overall: time complexity O(m*n)
        # overall: space complexity O(n)
        return res

    def longestCommonSubsequence(self, text1: str, text2: str) -> int:
        # Note:
        # Bottom Up Tabulation
        # 1. Initialize 2D Array -> dp[i][j] = LCS length for first i chars of text1, first j chars of text2
        # 2. Base Set Up -> dp[0][*] = 0, dp[*][0] = 0 (empty string has LCS = 0)
        # 3. Explore -> iterate i=1..m, j=1..n
        # 4. Explore Choices:
        #       if text1[i-1] == text2[j-1]: dp[i][j] = 1 + dp[i-1][j-1]
        #       else: dp[i][j] = max(dp[i-1][j], dp[i][j-1])
        # 5. Build -> fill dp row by row
        # Result: dp[m][n] = LCS length for full strings

        m, n = len(text1), len(text2)

        # Initialize Array -> size (m+1) x (n+1) for base row/col
        dp = [[0] * (n+1) for _ in range(m+1)]

        # Process -> iterate through chars of both strings
        for i in range(1, m+1):
            for j in range(1, n+1):

                # Explore Choices
                if text1[i-1] == text2[j-1]:
                    # Characters match -> extend subsequence
                    dp[i][j] = 1 + dp[i-1][j-1]
                else:
                    # Skip one from either string
                    dp[i][j] = max(dp[i-1][j], dp[i][j-1])

        # Result -> LCS length for full strings
        res = dp[m][n]

        # overall: time complexity O(m*n)
        # overall: space complexity O(m*n)
        return res

    def longestCommonSubsequence(self, text1: str, text2: str) -> int:
        # Note:
        # Bottom Up Variables (row compression)
        # 1. Only previous row is needed at any time
        # 2. Initialize two rows -> prev, curr
        # 3. Explore -> for each i, build row j=1..n
        # 4. Explore Choices:
        #       if text1[i-1] == text2[j-1]: curr[j] = 1 + prev[j-1]
        #       else: curr[j] = max(prev[j], curr[j-1])
        # 5. Slide -> prev = curr
        # Result: prev[n] = LCS length for full strings

        m, n = len(text1), len(text2)

        # Initialize two rows
        prev = [0] * (n+1)

        # Process -> iterate rows
        for i in range(1, m+1):
            curr = [0] * (n+1)
            for j in range(1, n+1):

                # Explore Choices
                if text1[i-1] == text2[j-1]:
                    curr[j] = 1 + prev[j-1]
                else:
                    curr[j] = max(prev[j], curr[j-1])

            # Slide -> update row
            prev = curr

        # Result -> LCS length
        res = prev[n]

        # overall: time complexity O(m*n)
        # overall: space complexity O(n)
        return res

    def longestCommonSubsequence(self, text1: str, text2: str) -> int:
        intersection = set(text1) & set(text2)
        if len(intersection) == 0: return 0
        t1 = [char for char in text1 if char in intersection]
        t2 = [char for char in text2 if char in intersection]
        dp = [0] * len(t2)
        for char in t1:
            count = 0
            for j in range(len(t2)):
                if dp[j]>count:
                    count=dp[j]
                elif t2[j] == char:
                    dp[j] = count + 1
        return max(dp)

    def maxProfit(self, prices: List[int]) -> int:

        # Note:
        # Bottom Up Tabulation
        # Three states per day:
        #   1. hold[i]    -> max profit at day i if holding stock
        #   2. sold[i]    -> max profit at day i if just sold stock (cooldown next day)
        #   3. rest[i]    -> max profit at day i if in cooldown or not holding
        #
        # Transitions:
        #   hold[i] = max(hold[i-1], rest[i-1] - prices[i])   # buy or continue holding
        #   sold[i] = hold[i-1] + prices[i]                   # sell today
        #   rest[i] = max(rest[i-1], sold[i-1])               # cooldown or stay at rest
        #
        # Base Set Up:
        #   hold[0] = -prices[0]   # buy first day
        #   sold[0] = 0            # cannot sell on day 0
        #   rest[0] = 0            # do nothing
        #
        # Result: max(sold[n-1], rest[n-1])  # must end not holding stock

        n = len(prices)

        # Initialize Arrays -> track 3 states per day
        hold = [0] * n
        sold = [0] * n
        rest = [0] * n

        # Base Set Up -> day 0
        hold[0] = -prices[0]
        sold[0] = 0
        rest[0] = 0

        # Process -> day 1 to n-1
        for i in range(1, n):

            # Transition: continue holding or buy today
            hold[i] = max(hold[i-1], rest[i-1] - prices[i])

            # Transition: sell today
            sold[i] = hold[i-1] + prices[i]

            # Transition: cooldown or rest
            rest[i] = max(rest[i-1], sold[i-1])

        # Result -> max profit if not holding stock
        res = max(sold[n-1], rest[n-1])

        # overall: time complexity O(n)
        # overall: space complexity O(n)
        return res

    def maxProfit(self, prices: List[int]) -> int:

        n = len(prices)
        if n == 1: return 0
        b = [-10 ** 9] * n
        s = [0] * n
        for i in range(n):
            s[i] = max(s[i - 1], prices[i] + b[i - 1])
            b[i] = max(b[i - 1], s[i - 2] - prices[i])
        return s[-1]

def maxProfit(self, prices: List[int]) -> int:

        # Note:
        # Bottom Up Variables (rolling states)
        # Three states tracked in variables:
        #   hold -> max profit holding stock
        #   sold -> max profit just sold (cooldown next day)
        #   rest -> max profit cooldown / not holding
        #
        # Transitions:
        #   new_hold = max(hold, rest - prices[i])
        #   new_sold = hold + prices[i]
        #   new_rest = max(rest, sold)
        #
        # Base Set Up:
        #   hold = -prices[0]
        #   sold = 0
        #   rest = 0
        #
        # Result: max(sold, rest)

        n = len(prices)

        # Base Set Up -> day 0
        hold = -prices[0]
        sold = 0
        rest = 0

        # Process -> day 1 to n-1
        for i in range(1, n):

            # Save previous states
            prev_hold, prev_sold, prev_rest = hold, sold, rest

            # Transitions
            hold = max(prev_hold, prev_rest - prices[i])
            sold = prev_hold + prices[i]
            rest = max(prev_rest, prev_sold)

        # Result -> max profit not holding stock
        res = max(sold, rest)

        # overall: time complexity O(n)
        # overall: space complexity O(1)
        return res

    def change(self, amount: int, coins: List[int]) -> int:
        # Note:
        # Bottom Up Tabulation (2D DP)
        # dp[i][j] = number of ways to make sum j using first i coins
        #
        # Transitions:
        #   if coin value > j:
        #       dp[i][j] = dp[i-1][j]            # cannot take coin i
        #   else:
        #       dp[i][j] = dp[i-1][j] + dp[i][j-coin] 
        #           -> ways without this coin + ways including this coin
        #
        # Base Set Up:
        #   dp[0][0] = 1    # one way to make amount 0 (use no coins)
        #   dp[0][j>0] = 0  # cannot make positive amount with 0 coins
        #
        # Result: dp[n][amount]

        n = len(coins)
        dp = [[0] * (amount + 1) for _ in range(n + 1)]
        
        # base setup: one way to make 0
        for i in range(n + 1):
            dp[i][0] = 1
        
        # process
        for i in range(1, n + 1):
            for j in range(1, amount + 1):
                if j < coins[i-1]:
                    dp[i][j] = dp[i-1][j]
                else:
                    dp[i][j] = dp[i-1][j] + dp[i][j - coins[i-1]]
        
        return dp[n][amount]

    def change(self, amount: int, coins: List[int]) -> int:
        # Note:
        # Optimized Bottom Up (1D DP)
        # dp[j] = number of ways to make sum j
        #
        # Transitions:
        #   dp[j] += dp[j - coin]   # add ways using this coin
        #
        # Base Set Up:
        #   dp[0] = 1  # one way to make amount 0
        #
        # Result: dp[amount]

        dp = [0] * (amount + 1)
        dp[0] = 1
        
        for coin in coins:
            for j in range(coin, amount + 1):
                dp[j] += dp[j - coin]
        
        return dp[amount]

    def change(self, amount: int, coins: List[int]) -> int:
        # Note:
        # DP State is "first i elements" style -> dp[i][sum]
        # dp[i][s] = number of ways to reach sum s using nums[0..i-1]
        #
        # Transition:
        #   dp[i][s] = dp[i-1][s - nums[i-1]] + dp[i-1][s + nums[i-1]]
        #
        # Base:
        #   dp[0][0] = 1  (no numbers, only one way to make sum 0)
        #
        # Result:
        #   dp[n][target]
        #
        # DP size:
        #   total sum range = [-total, total] → shift by offset = total
        #   index = s + offset

        total = sum(nums)
        if abs(target) > total: return 0
        offset = total
        n = len(nums)

        dp = [[0] * (2 * total + 1) for _ in range(n + 1)]
        dp[0][0 + offset] = 1

        for i in range(1, n + 1):
            num = nums[i - 1]
            for s in range(-total, total + 1):
                if dp[i - 1][s + offset] != 0:
                    dp[i][s + num + offset] += dp[i - 1][s + offset]
                    dp[i][s - num + offset] += dp[i - 1][s + offset]

        return dp[n][target + offset]

    def findTargetSumWays(self, nums: List[int], target: int) -> int:

        # Note:
        # Same as Solution 1, but optimize to 1D array (rolling state)
        # dp[s] = number of ways to reach sum s at current step
        # Must use temp array to avoid overwriting

        total = sum(nums)
        if abs(target) > total: return 0
        offset = total

        dp = [0] * (2 * total + 1)
        dp[0 + offset] = 1

        for num in nums:
            next_dp = [0] * (2 * total + 1)
            for s in range(-total, total + 1):
                if dp[s + offset] != 0:
                    next_dp[s + num + offset] += dp[s + offset]
                    next_dp[s - num + offset] += dp[s + offset]
            dp = next_dp

        return dp[target + offset]

    def findTargetSumWays(self, nums: List[int], target: int) -> int:

        # Note:
        # Transform into subset sum:
        # Let P = sum(positive nums), N = sum(negative nums)
        # Then P - N = target and P + N = total
        # → P = (target + total) / 2
        #
        # Count number of subsets that sum to P
        #
        # dp[s] = number of ways to reach sum s using subset of nums

        total = sum(nums)
        if total < abs(target) or (target + total) % 2 != 0: return 0
        P = (target + total) // 2

        dp = [0] * (P + 1)
        dp[0] = 1

        for num in nums:
            for s in range(P, num - 1, -1):
                dp[s] += dp[s - num]

        return dp[P]

    def isInterleave(self, s1: str, s2: str, s3: str) -> bool:
        # Note:
        # DP State:
        #   dp[i][j] = True if s3[0..i+j-1] can be formed 
        #              by interleaving s1[0..i-1] and s2[0..j-1]
        #
        # Transition:
        #   dp[i][j] = (dp[i-1][j] and s1[i-1] == s3[i+j-1]) 
        #            or (dp[i][j-1] and s2[j-1] == s3[i+j-1])
        #
        # Base:
        #   dp[0][0] = True
        #
        # Result:
        #   dp[len(s1)][len(s2)]

        n1, n2, n3 = len(s1), len(s2), len(s3)
        if n1 + n2 != n3: return False

        dp = [[False] * (n2 + 1) for _ in range(n1 + 1)]
        dp[0][0] = True

        for i in range(n1 + 1):
            for j in range(n2 + 1):
                if i > 0 and s1[i-1] == s3[i+j-1]:
                    dp[i][j] |= dp[i-1][j]
                if j > 0 and s2[j-1] == s3[i+j-1]:
                    dp[i][j] |= dp[i][j-1]

        return dp[n1][n2]

    def isInterleave(self, s1: str, s2: str, s3: str) -> bool:
        # Note:
        # Space optimized version of Solution 1
        # dp[j] = True if prefix of s1[0..i-1] and s2[0..j-1]
        #         can form s3[0..i+j-1]
        #
        # Roll through s1, update dp in place

        n1, n2, n3 = len(s1), len(s2), len(s3)
        if n1 + n2 != n3: return False

        dp = [False] * (n2 + 1)
        dp[0] = True

        for j in range(1, n2 + 1):
            dp[j] = dp[j-1] and s2[j-1] == s3[j-1]

        for i in range(1, n1 + 1):
            dp[0] = dp[0] and s1[i-1] == s3[i-1]
            for j in range(1, n2 + 1):
                dp[j] = (dp[j] and s1[i-1] == s3[i+j-1]) or \
                        (dp[j-1] and s2[j-1] == s3[i+j-1])

        return dp[n2]

    def longestIncreasingPath(self, matrix: List[List[int]]) -> int:
        # Notes:
        # - Use DFS with memoization to avoid recomputation.
        # - Each cell (i, j) stores the length of the longest increasing path starting there.
        # - Explore 4 directions: up, down, left, right if the next cell is larger.
        #
        # Result: max value across all cells in memo

        if not matrix or not matrix[0]:
            return 0
        
        m, n = len(matrix), len(matrix[0])
        memo = [[0] * n for _ in range(m)]  # memo[i][j] = longest path starting from (i, j)

        directions = [(1, 0), (-1, 0), (0, 1), (0, -1)]

        def dfs(i, j):
            # Return cached result
            if memo[i][j] != 0:
                return memo[i][j]
            
            # At least the cell itself
            best = 1
            for dx, dy in directions:
                x, y = i + dx, j + dy
                if 0 <= x < m and 0 <= y < n and matrix[x][y] > matrix[i][j]:
                    best = max(best, 1 + dfs(x, y))
            
            memo[i][j] = best
            return best

        res = 0
        for i in range(m):
            for j in range(n):
                res = max(res, dfs(i, j))
        return res

    def longestIncreasingPath(self, matrix: List[List[int]]) -> int:
        # Notes:
        # - Treat each cell as a node in a DAG.
        # - Edges go from smaller value -> larger value neighbor.
        # - Topological sorting via Kahn's algorithm counts layers = path length.
        #
        # Result: number of BFS layers processed.

        if not matrix or not matrix[0]:
            return 0

        m, n = len(matrix), len(matrix[0])
        indegree = [[0] * n for _ in range(m)]
        directions = [(1, 0), (-1, 0), (0, 1), (0, -1)]

        # Compute indegree for each cell
        for i in range(m):
            for j in range(n):
                for dx, dy in directions:
                    x, y = i + dx, j + dy
                    if 0 <= x < m and 0 <= y < n and matrix[x][y] > matrix[i][j]:
                        indegree[x][y] += 1

        # Collect nodes with indegree 0
        q = deque()
        for i in range(m):
            for j in range(n):
                if indegree[i][j] == 0:
                    q.append((i, j))

        res = 0
        # BFS layer by layer
        while q:
            res += 1
            for _ in range(len(q)):
                i, j = q.popleft()
                for dx, dy in directions:
                    x, y = i + dx, j + dy
                    if 0 <= x < m and 0 <= y < n and matrix[x][y] > matrix[i][j]:
                        indegree[x][y] -= 1
                        if indegree[x][y] == 0:
                            q.append((x, y))
        return res

    def numDistinct(self, s: str, t: str) -> int:
        # Notes:
        # - dp[i][j] = number of subsequences of s[:i] that equals t[:j]
        # - Transitions:
        #     if s[i-1] == t[j-1]:
        #         dp[i][j] = dp[i-1][j-1] + dp[i-1][j]
        #     else:
        #         dp[i][j] = dp[i-1][j]
        # - Base cases:
        #     dp[i][0] = 1   (empty t can always be formed)
        #     dp[0][j] = 0   (non-empty t cannot be formed from empty s)
        #
        # Result: dp[m][n]

        m, n = len(s), len(t)
        dp = [[0] * (n + 1) for _ in range(m + 1)]

        # Base: empty t
        for i in range(m + 1):
            dp[i][0] = 1

        for i in range(1, m + 1):
            for j in range(1, n + 1):
                if s[i - 1] == t[j - 1]:
                    dp[i][j] = dp[i - 1][j - 1] + dp[i - 1][j]
                else:
                    dp[i][j] = dp[i - 1][j]
        
        return dp[m][n]

    def numDistinct(self, s: str, t: str) -> int:
        # Notes:
        # - Optimize to 1D by rolling over dp for target string.
        # - Iterate j backwards to avoid overwriting needed states.
        #
        # Result: dp[n] (subsequences of s forming full t)

        m, n = len(s), len(t)
        dp = [0] * (n + 1)
        dp[0] = 1  # empty t

        for i in range(1, m + 1):
            # iterate backwards for correctness
            for j in range(n, 0, -1):
                if s[i - 1] == t[j - 1]:
                    dp[j] += dp[j - 1]
        
        return dp[n]

    def numDistinct(self, s: str, t: str) -> int:
        n, m = len(s), len(t)
        cache = {}
        def rec(x=0, y=0) -> int:
            if y == m:
                return 1
            
            if (n - x) < (m - y):
                return 0

            if (x, y) not in cache:
                cache[(x, y)] = rec(x+1, y) + (rec(x+1, y+1) if s[x] == t[y] else 0)
            return cache[(x, y)]
        return rec()

    def minDistance(self, word1: str, word2: str) -> int:
        # Notes:
        # - dp[i][j] = minimum edit distance to convert word1[:i] to word2[:j]
        # - Operations:
        #     1. Insert:  dp[i][j-1] + 1
        #     2. Delete:  dp[i-1][j] + 1
        #     3. Replace: dp[i-1][j-1] + (0 if same else 1)
        #
        # Base cases:
        # - dp[0][j] = j (convert empty word1 to word2[:j] by inserting)
        # - dp[i][0] = i (convert word1[:i] to empty by deleting)
        #
        # Result: dp[m][n]

        m, n = len(word1), len(word2)
        dp = [[0] * (n + 1) for _ in range(m + 1)]

        # Base initialization
        for i in range(m + 1):
            dp[i][0] = i
        for j in range(n + 1):
            dp[0][j] = j

        # Fill dp table
        for i in range(1, m + 1):
            for j in range(1, n + 1):
                if word1[i - 1] == word2[j - 1]:
                    dp[i][j] = dp[i - 1][j - 1]
                else:
                    dp[i][j] = min(
                        dp[i - 1][j] + 1,     # delete
                        dp[i][j - 1] + 1,     # insert
                        dp[i - 1][j - 1] + 1  # replace
                    )

        return dp[m][n]

    def minDistance(self, word1: str, word2: str) -> int:
        # Notes:
        # - Optimize to 1D DP by rolling rows.
        # - Keep prev row and update current row iteratively.
        #
        # Result: dp[n]

        m, n = len(word1), len(word2)

        prev = list(range(n + 1))  # dp[0][j]
        curr = [0] * (n + 1)

        for i in range(1, m + 1):
            curr[0] = i  # base: delete all chars of word1[:i]
            for j in range(1, n + 1):
                if word1[i - 1] == word2[j - 1]:
                    curr[j] = prev[j - 1]
                else:
                    curr[j] = min(
                        prev[j] + 1,     # delete
                        curr[j - 1] + 1, # insert
                        prev[j - 1] + 1  # replace
                    )
            prev, curr = curr, prev  # swap

        return prev[n]

    def minDistance(self, word1: str, word2: str) -> int:
        # Notes:
        # - Recursive definition:
        #   dfs(i, j) = min edit distance between word1[:i] and word2[:j]
        # - Base cases:
        #   if i == 0: return j  (insert all j chars)
        #   if j == 0: return i  (delete all i chars)
        # - If last chars equal: dfs(i, j) = dfs(i-1, j-1)
        # - Else: min(insert, delete, replace)
        #
        # - Manual memoization using dictionary

        memo = {}
        m, n = len(word1), len(word2)

        def dfs(i, j):
            if (i, j) in memo:
                return memo[(i, j)]

            if i == 0:
                return j
            if j == 0:
                return i

            if word1[i - 1] == word2[j - 1]:
                memo[(i, j)] = dfs(i - 1, j - 1)
            else:
                memo[(i, j)] = min(
                    dfs(i - 1, j) + 1,     # delete
                    dfs(i, j - 1) + 1,     # insert
                    dfs(i - 1, j - 1) + 1  # replace
                )
            return memo[(i, j)]

        return dfs(m, n)

    def maxCoins(self, nums: List[int]) -> int:
        # Note:
        # Bottom Up DP / Interval DP
        # 1. Pad Array -> add 1 to both ends to simplify edge calculations
        # 2. dp[i][j] -> max coins from bursting balloons in nums[i:j+1] exclusive
        # 3. Iterate -> all intervals length 1 to n
        # 4. Explore Choices -> last balloon to burst in interval k
        # 5. Build -> dp[i][j] = max(dp[i][k-1] + nums[i]*nums[k]*nums[j] + dp[k+1][j])
        # Result: dp[0][n-1] holds max coins for full interval

        n = len(nums)
        # Pad nums with 1 at both ends
        nums = [1] + nums + [1]
        n += 2

        # Initialize dp array -> max coins for interval i->j
        dp = [[0] * n for _ in range(n)]

        # Process -> interval lengths 1 to n-2 (excluding padded 1s)
        for length in range(1, n-1):
            for left in range(1, n - length):
                right = left + length - 1

                # Explore Choices -> last balloon to burst in interval
                for k in range(left, right + 1):
                    # Build -> max coins considering bursting k last
                    dp[left][right] = max(
                        dp[left][right],
                        nums[left-1]*nums[k]*nums[right+1] + dp[left][k-1] + dp[k+1][right]
                    )

        # Result -> max coins for interval 1 -> n-2
        res = dp[1][n-2]
        return res

    def maxCoins(self, nums: List[int]) -> int:
        # Note:
        # Bottom Up Interval DP
        # 1. Pad Array -> simplify edge cases
        # 2. dp[i][j] -> max coins interval i->j exclusive
        # 3. Iterate -> interval lengths 1 to n-2
        # 4. Explore Choices -> last balloon k to burst in interval
        # 5. Build -> dp[i][j] = max(dp[i][k-1] + nums[i]*nums[k]*nums[j] + dp[k+1][j])
        # Result: dp[1][n-2] holds max coins

        n = len(nums)
        nums = [1] + nums + [1]
        n += 2

        dp = [[0]*n for _ in range(n)]

        for length in range(1, n-1):
            for left in range(1, n - length):
                right = left + length - 1
                for k in range(left, right+1):
                    dp[left][right] = max(
                        dp[left][right],
                        nums[left-1]*nums[k]*nums[right+1] + dp[left][k-1] + dp[k+1][right]
                    )

        res = dp[1][n-2]
        return res

    def maxCoins(self, nums: List[int]) -> int:
        # Note:
        # Bottom Up Interval DP Space Optimized
        # 1. Pad Array -> simplify edge cases
        # 2. Process intervals iteratively using 2D dp
        # 3. Explore Choices -> last balloon k to burst
        # 4. Build -> dp[left][right] = max(dp[left][k-1] + nums[left-1]*nums[k]*nums[right+1] + dp[k+1][right])
        # 5. Use only necessary interval slices to reduce memory footprint
        # Result: max coins for full interval

        n = len(nums)
        nums = [1] + nums + [1]
        n += 2

        dp = [[0]*n for _ in range(n)]

        for length in range(1, n-1):
            for left in range(1, n - length):
                right = left + length - 1
                max_coins = 0
                for k in range(left, right+1):
                    coins = nums[left-1]*nums[k]*nums[right+1] + dp[left][k-1] + dp[k+1][right]
                    if coins > max_coins:
                        max_coins = coins
                dp[left][right] = max_coins

        res = dp[1][n-2]
        return res

    def isMatch(self, s: str, p: str) -> bool:
        # Note:
        # Top Down DP / Memoized Recursion
        # 1. dfs(i,j) -> does s[i:] match p[j:]
        # 2. Explore Choices -> '*' zero or more preceding char, '.' single char
        # 3. Build -> check match current char and recurse
        # 4. Memo Return -> store result for (i,j) to avoid recomputation
        # Result: match for full strings

        memo = {}

        def dfs(i, j):
            if (i,j) in memo:
                return memo[(i,j)]
            if j == len(p):
                memo[(i,j)] = i == len(s)
                return memo[(i,j)]
            match = i < len(s) and (s[i] == p[j] or p[j] == '.')
            if j+1 < len(p) and p[j+1] == '*':
                memo[(i,j)] = dfs(i, j+2) or (match and dfs(i+1, j))
            else:
                memo[(i,j)] = match and dfs(i+1, j+1)
            return memo[(i,j)]

        res = dfs(0,0)
        return res

    def isMatch(self, s: str, p: str) -> bool:
        # Note:
        # Bottom Up DP / Tabulation
        # 1. dp[i][j] -> does s[0..i-1] match p[0..j-1]
        # 2. Base Set Up -> dp[0][0] = True (empty matches empty)
        # 3. Explore -> fill dp table considering '*' and '.' rules
        # 4. Build -> handle '*' zero or more, '.' matches any char
        # Result: dp[len(s)][len(p)]

        m, n = len(s), len(p)
        dp = [[False]*(n+1) for _ in range(m+1)]
        dp[0][0] = True

        for j in range(2, n+1):
            if p[j-1] == '*':
                dp[0][j] = dp[0][j-2]

        for i in range(1, m+1):
            for j in range(1, n+1):
                if p[j-1] == '*':
                    dp[i][j] = dp[i][j-2] or (dp[i-1][j] and (s[i-1]==p[j-2] or p[j-2]=='.'))
                else:
                    dp[i][j] = dp[i-1][j-1] and (s[i-1]==p[j-1] or p[j-1]=='.')

        res = dp[m][n]
        return res

    def isMatch(self, s: str, p: str) -> bool:
        # Note:
        # Bottom Up DP Space Optimized
        # 1. Use two rows to store dp[i-1] and dp[i] to save space
        # 2. dp[j] -> does current row s[0..i] match p[0..j-1]
        # 3. Explore -> '*' and '.' rules applied for each column
        # 4. Slide window -> update previous row after each s[i]
        # Result: dp[len(s)][len(p)]

        m, n = len(s), len(p)
        prev = [False]*(n+1)
        curr = [False]*(n+1)
        prev[0] = True

        for j in range(2, n+1):
            if p[j-1] == '*':
                prev[j] = prev[j-2]

        for i in range(1, m+1):
            curr[0] = False
            for j in range(1, n+1):
                if p[j-1] == '*':
                    curr[j] = curr[j-2] or (prev[j] and (s[i-1]==p[j-2] or p[j-2]=='.'))
                else:
                    curr[j] = prev[j-1] and (s[i-1]==p[j-1] or p[j-1]=='.')
            prev, curr = curr, [False]*(n+1)

        res = prev[n]
        return res

    def isMatch(self, s: str, p: str) -> bool:
        if not p:
            return not s
        first = bool(s) and (s[0] == p[0] or p[0] == '.')
        if len(p) >= 2 and p[1] == '*':
            return self.isMatch(s, p[2:]) or (first and self.isMatch(s[1:], p))
        return first and self.isMatch(s[1:], p[1:])