Dynamic Programming

from functools import lru_cache

def coin_change_memo(coins, amount):
    """Fewest coins to make amount, or -1."""
    @lru_cache(maxsize=None)
    def go(rem):
        if rem == 0:
            return 0
        if rem < 0:
            return float("inf")
        return min((go(rem - c) + 1 for c in coins), default=float("inf"))

    res = go(amount)
    return -1 if res == float("inf") else res

def coin_change_table(coins, amount):
    INF = float("inf")
    dp = [INF] * (amount + 1)
    dp[0] = 0
    for rem in range(1, amount + 1):
        for c in coins:
            if c <= rem and dp[rem - c] + 1 < dp[rem]:
                dp[rem] = dp[rem - c] + 1
    return -1 if dp[amount] == INF else dp[amount]

def climb_stairs(n):
    """dp[i] = dp[i-1] + dp[i-2], rolled to two variables. O(1) space."""
    a, b = 1, 1                        # dp[0], dp[1]
    for _ in range(2, n + 1):
        a, b = b, a + b
    return b

def rob(nums):
    """House Robber. Cannot take adjacent houses."""
    take, skip = 0, 0
    for x in nums:
        take, skip = skip + x, max(skip, take)
    return max(take, skip)

def rob_circular(nums):
    """Houses in a circle: either the first is out or the last is out."""
    if len(nums) == 1:
        return nums[0]
    return max(rob(nums[1:]), rob(nums[:-1]))

def max_subarray(nums):
    """Kadane. dp[i] = max(nums[i], dp[i-1] + nums[i])."""
    best = cur = nums[0]
    for x in nums[1:]:
        cur = max(x, cur + x)
        best = max(best, cur)
    return best

def decode_ways(s):
    """Count decodings of a digit string to letters A-Z."""
    if not s or s[0] == "0":
        return 0
    prev2, prev1 = 1, 1
    for i in range(1, len(s)):
        cur = 0
        if s[i] != "0":
            cur += prev1                          # single digit
        if 10 <= int(s[i - 1:i + 1]) <= 26:
            cur += prev2                          # two digits
        prev2, prev1 = prev1, cur
        if cur == 0:
            return 0
    return prev1

def word_break(s, word_dict):
    """dp[i] = can the prefix of length i be segmented?"""
    words = set(word_dict)
    n = len(s)
    dp = [False] * (n + 1)
    dp[0] = True
    for i in range(1, n + 1):
        for j in range(i):
            if dp[j] and s[j:i] in words:
                dp[i] = True
                break
    return dp[n]

def unique_paths(m, n):
    """Only right and down moves. Rolled to one row, O(n) space."""
    row = [1] * n
    for _ in range(1, m):
        for c in range(1, n):
            row[c] += row[c - 1]        # row[c] is up, row[c-1] is left
    return row[-1]

def min_path_sum(grid):
    """Minimum sum from the top-left to the bottom-right."""
    rows, cols = len(grid), len(grid[0])
    dp = [float("inf")] * cols
    dp[0] = 0
    for r in range(rows):
        dp[0] += grid[r][0]
        for c in range(1, cols):
            dp[c] = min(dp[c], dp[c - 1]) + grid[r][c]
    return dp[-1]

def maximal_square(matrix):
    """Largest all-1 square. dp[r][c] is the side length ending at (r, c)."""
    rows, cols = len(matrix), len(matrix[0])
    dp = [[0] * (cols + 1) for _ in range(rows + 1)]
    best = 0
    for r in range(1, rows + 1):
        for c in range(1, cols + 1):
            if matrix[r - 1][c - 1] == "1":
                dp[r][c] = 1 + min(dp[r - 1][c], dp[r][c - 1], dp[r - 1][c - 1])
                best = max(best, dp[r][c])
    return best * best

def knapsack_01(weights, values, capacity):
    """Each item at most once. O(n * W) time, O(W) space."""
    dp = [0] * (capacity + 1)
    for w, v in zip(weights, values):
        for c in range(capacity, w - 1, -1):        # DESCENDING
            dp[c] = max(dp[c], dp[c - w] + v)
    return dp[capacity]

def knapsack_unbounded(weights, values, capacity):
    """Unlimited copies. Same loop, ASCENDING."""
    dp = [0] * (capacity + 1)
    for w, v in zip(weights, values):
        for c in range(w, capacity + 1):            # ASCENDING
            dp[c] = max(dp[c], dp[c - w] + v)
    return dp[capacity]

def knapsack_01_2d(weights, values, capacity):
    """Full table, so the chosen items can be reconstructed."""
    n = len(weights)
    dp = [[0] * (capacity + 1) for _ in range(n + 1)]
    for i in range(1, n + 1):
        w, v = weights[i - 1], values[i - 1]
        for c in range(capacity + 1):
            dp[i][c] = dp[i - 1][c]                 # skip item i
            if w <= c:
                dp[i][c] = max(dp[i][c], dp[i - 1][c - w] + v)   # take it
    # reconstruct
    chosen, c = [], capacity
    for i in range(n, 0, -1):
        if dp[i][c] != dp[i - 1][c]:
            chosen.append(i - 1)
            c -= weights[i - 1]
    return dp[n][capacity], chosen[::-1]

def can_partition(nums):
    """Split into two equal-sum halves. 0/1 subset-sum feasibility."""
    total = sum(nums)
    if total % 2:
        return False
    target = total // 2
    dp = [False] * (target + 1)
    dp[0] = True
    for x in nums:
        for c in range(target, x - 1, -1):
            dp[c] = dp[c] or dp[c - x]
    return dp[target]

def coin_change_combinations(coins, amount):
    """Count COMBINATIONS. Coins outer, so order does not matter."""
    dp = [0] * (amount + 1)
    dp[0] = 1
    for c in coins:
        for a in range(c, amount + 1):
            dp[a] += dp[a - c]
    return dp[amount]

def combination_sum_permutations(nums, target):
    """Count PERMUTATIONS. Target outer, so order matters."""
    dp = [0] * (target + 1)
    dp[0] = 1
    for a in range(1, target + 1):
        for x in nums:
            if x <= a:
                dp[a] += dp[a - x]
    return dp[target]

def lis_quadratic(nums):
    """O(n^2). dp[i] = LIS length ending exactly at i."""
    if not nums:
        return 0
    dp = [1] * len(nums)
    for i in range(1, len(nums)):
        for j in range(i):
            if nums[j] < nums[i]:
                dp[i] = max(dp[i], dp[j] + 1)
    return max(dp)

def lis_patience(nums):
    """O(n log n). tails[k] = smallest possible tail of an LIS of length k+1.
    bisect_left gives strictly increasing, bisect_right gives non-decreasing."""
    import bisect
    tails = []
    for x in nums:
        i = bisect.bisect_left(tails, x)
        if i == len(tails):
            tails.append(x)
        else:
            tails[i] = x               # a smaller tail keeps more room open
    return len(tails)

def lis_reconstruct(nums):
    """O(n log n) length plus the actual subsequence."""
    import bisect
    tails, tail_idx, parent = [], [], [-1] * len(nums)
    for i, x in enumerate(nums):
        k = bisect.bisect_left(tails, x)
        if k == len(tails):
            tails.append(x)
            tail_idx.append(i)
        else:
            tails[k] = x
            tail_idx[k] = i
        parent[i] = tail_idx[k - 1] if k > 0 else -1
    out, cur = [], tail_idx[-1] if tail_idx else -1
    while cur != -1:
        out.append(nums[cur])
        cur = parent[cur]
    return out[::-1]

def lcs(a, b):
    """Longest common subsequence length. O(nm) time, O(min) space rolled."""
    n, m = len(a), len(b)
    prev = [0] * (m + 1)
    for i in range(1, n + 1):
        cur = [0] * (m + 1)
        for j in range(1, m + 1):
            if a[i - 1] == b[j - 1]:
                cur[j] = prev[j - 1] + 1
            else:
                cur[j] = max(prev[j], cur[j - 1])
        prev = cur
    return prev[m]

def edit_distance(a, b):
    """Levenshtein. Insert, delete, replace each cost 1. O(nm), O(m) space."""
    n, m = len(a), len(b)
    prev = list(range(m + 1))              # deleting all of b's prefix
    for i in range(1, n + 1):
        cur = [i] + [0] * m                # deleting all of a's prefix
        for j in range(1, m + 1):
            if a[i - 1] == b[j - 1]:
                cur[j] = prev[j - 1]       # free match
            else:
                cur[j] = 1 + min(prev[j - 1],   # replace
                                 prev[j],       # delete from a
                                 cur[j - 1])    # insert into a
        prev = cur
    return prev[m]

def longest_palindromic_subsequence(s):
    """LCS of s with its reverse."""
    return lcs(s, s[::-1])

def longest_common_substring(a, b):
    """CONTIGUOUS, so a mismatch resets to 0 rather than carrying forward."""
    n, m = len(a), len(b)
    prev = [0] * (m + 1)
    best = 0
    for i in range(1, n + 1):
        cur = [0] * (m + 1)
        for j in range(1, m + 1):
            if a[i - 1] == b[j - 1]:
                cur[j] = prev[j - 1] + 1
                best = max(best, cur[j])
        prev = cur
    return best

def burst_balloons(nums):
    """Interval DP. Iterate by LENGTH, and pick the LAST balloon burst
    in each interval so the neighbors are known. O(n^3)."""
    a = [1] + nums + [1]
    n = len(a)
    dp = [[0] * n for _ in range(n)]
    for length in range(2, n):
        for lo in range(n - length):
            hi = lo + length
            for k in range(lo + 1, hi):
                dp[lo][hi] = max(dp[lo][hi],
                                 dp[lo][k] + a[lo] * a[k] * a[hi] + dp[k][hi])
    return dp[0][n - 1]

def tsp_bitmask(dist):
    """Shortest tour visiting every city. O(2^n * n^2)."""
    n = len(dist)
    INF = float("inf")
    dp = [[INF] * n for _ in range(1 << n)]
    dp[1][0] = 0                        # started at city 0
    for mask in range(1 << n):
        for u in range(n):
            if dp[mask][u] == INF or not (mask >> u) & 1:
                continue
            for v in range(n):
                if (mask >> v) & 1:
                    continue
                nm = mask | (1 << v)
                cand = dp[mask][u] + dist[u][v]
                if cand < dp[nm][v]:
                    dp[nm][v] = cand
    full = (1 << n) - 1
    return min(dp[full][u] + dist[u][0] for u in range(n))

def stock_with_cooldown(prices):
    """State machine: holding, just sold (cooldown), free. O(n), O(1)."""
    hold, sold, free = float("-inf"), 0, 0
    for p in prices:
        hold, sold, free = (max(hold, free - p),   # keep or buy
                            hold + p,               # sell
                            max(free, sold))        # rest or exit cooldown
    return max(sold, free)

def max_profit_k_transactions(prices, k):
    """At most k buy-sell pairs. O(nk) time, O(k) space."""
    if not prices or k == 0:
        return 0
    if k >= len(prices) // 2:                       # unlimited, greedy sum
        return sum(max(0, b - a) for a, b in zip(prices, prices[1:]))
    buy = [float("-inf")] * (k + 1)
    sell = [0] * (k + 1)
    for p in prices:
        for t in range(1, k + 1):
            buy[t] = max(buy[t], sell[t - 1] - p)
            sell[t] = max(sell[t], buy[t] + p)
    return sell[k]

// Java memoization: an int[][] with a sentinel beats a HashMap for speed
int[][] memo = new int[n][m];
for (int[] row : memo) Arrays.fill(row, -1);

int go(int i, int j) {
    if (i == n || j == m) return 0;
    if (memo[i][j] != -1) return memo[i][j];
    int res = a.charAt(i) == b.charAt(j)
        ? 1 + go(i + 1, j + 1)
        : Math.max(go(i + 1, j), go(i, j + 1));
    return memo[i][j] = res;
}