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)."""
    # TODO: build a 2D dp table of size (len(a) + 1) by (len(b) + 1).
    # Seed row 0 with j (all insertions) and column 0 with i (all deletions).
    # For each i, j: if a[i - 1] == b[j - 1] carry dp[i - 1][j - 1];
    # else 1 + min(delete dp[i - 1][j], insert dp[i][j - 1], replace dp[i - 1][j - 1]).
    # Return dp[len(a)][len(b)].
    pass