def climb_stairs(n):
    """Number of ways to climb n stairs taking 1 or 2 steps, using memoization."""
    memo = {}

    def ways(k):
        if k < 0:
            return 0
        if k == 0:
            return 1
        if k in memo:
            return memo[k]
        memo[k] = ways(k - 1) + ways(k - 2)
        return memo[k]

    return ways(n)


def coin_change(coins, amount):
    """Minimum number of coins to make amount, or -1 if impossible (tabulation)."""
    INF = amount + 1
    dp = [0] + [INF] * amount
    for a in range(1, amount + 1):
        for c in coins:
            if c <= a and dp[a - c] + 1 < dp[a]:
                dp[a] = dp[a - c] + 1
    return dp[amount] if dp[amount] != INF else -1


def knapsack(weights, values, capacity):
    """Max total value with total weight <= capacity (0/1 knapsack, tabulation)."""
    n = len(weights)
    dp = [[0] * (capacity + 1) for _ in range(n + 1)]
    for i in range(1, n + 1):
        w = weights[i - 1]
        v = values[i - 1]
        for cap in range(capacity + 1):
            dp[i][cap] = dp[i - 1][cap]
            if w <= cap and dp[i - 1][cap - w] + v > dp[i][cap]:
                dp[i][cap] = dp[i - 1][cap - w] + v
    return dp[n][capacity]


def edit_distance(a, b):
    """Levenshtein distance between a and b (insert/delete/replace cost 1)."""
    m = len(a)
    n = len(b)
    dp = [[0] * (n + 1) for _ in range(m + 1)]
    for i in range(m + 1):
        dp[i][0] = i
    for j in range(n + 1):
        dp[0][j] = j
    for i in range(1, m + 1):
        for j in range(1, n + 1):
            if a[i - 1] == b[j - 1]:
                dp[i][j] = dp[i - 1][j - 1]
            else:
                dp[i][j] = 1 + min(dp[i - 1][j], dp[i][j - 1], dp[i - 1][j - 1])
    return dp[m][n]


def longest_common_subsequence(a, b):
    """Length of the longest common subsequence of a and b (tabulation)."""
    # TODO: build a 2D dp table of size (len(a) + 1) by (len(b) + 1), all zeros.
    # For each i, j: if a[i - 1] == b[j - 1] then dp[i][j] = dp[i - 1][j - 1] + 1;
    # else dp[i][j] = max(dp[i - 1][j], dp[i][j - 1]).
    # Return dp[len(a)][len(b)].
    pass