Dynamic Programming

1. Climbing Stairs Easy

Problem

You climb a staircase of n steps, taking either 1 or 2 steps at a time. How many distinct ways are there to reach the top?

The five questions

1. State: ways[i] is the number of distinct ways to reach step i.
2. Recurrence: the last move was either a 1 from step i - 1 or a 2 from step i - 2, and those two sets of routes are disjoint, so ways[i] = ways[i - 1] + ways[i - 2].
3. Base: ways[1] = 1, ways[2] = 2.
4. Order: increasing i.
5. Answer: ways[n].

That is the Fibonacci sequence, offset by one. Saying so immediately is a good start.

Solution

def climb_stairs(n: int) -> int:
    """Number of distinct ways to climb n steps taking 1 or 2 at a time.

    Args:
        n: Number of steps, n >= 1.

    Returns:
        The count of distinct climbs.

    Example:
        >>> climb_stairs(5)
        8
    """
    if n <= 2:
        return n

    # Only the last two values are ever needed, so keep two variables
    # instead of an array. O(1) space.
    two_back, one_back = 1, 2

    for _ in range(3, n + 1):
        two_back, one_back = one_back, two_back + one_back

    return one_back

The progression to show

from functools import cache


def climb_stairs_memo(n: int) -> int:
    """Step 1: the brute force, made linear by one decorator."""

    @cache
    def ways(step: int) -> int:
        if step <= 2:
            return step
        return ways(step - 1) + ways(step - 2)

    return ways(n)


def climb_stairs_table(n: int) -> int:
    """Step 2: same thing bottom-up, O(n) space."""
    if n <= 2:
        return n

    ways = [0] * (n + 1)
    ways[1], ways[2] = 1, 2

    for i in range(3, n + 1):
        ways[i] = ways[i - 1] + ways[i - 2]

    return ways[n]

Brute force to memoised to tabulated to two variables. Walking an interviewer through that chain in ninety seconds demonstrates the method, which is what the question is for.

Variations you should expect

Edge cases to raise

• n = 1 gives 1, n = 2 gives 2. Both handled by the guard.
• n = 0: arguably 1, the empty climb. The guard returns 0. Ask which is wanted; it is a fair question.
• Large n: Python integers grow without limit, so no overflow, but the numbers get long. Worth a sentence.

2. Coin Change Medium

Problem

Given coin denominations and a target amount, return the fewest coins that sum to exactly that amount, or -1 if it is impossible. You have unlimited coins of each denomination.

Why greedy fails

The five questions

1. State: best[v] is the fewest coins summing to exactly v.
2. Recurrence: the last coin used was some c ≤ v, so best[v] = 1 + min(best[v - c]) over all such c.
3. Base: best[0] = 0. Zero coins make zero.
4. Order: increasing v, so best[v - c] is always ready.
5. Answer: best[amount], or -1 if it is still the sentinel.

Solution

def coin_change(coins: list[int], amount: int) -> int:
    """Fewest coins summing to exactly amount, or -1 if impossible.

    Args:
        coins: Distinct positive denominations, unlimited supply of each.
        amount: Target sum, amount >= 0.

    Returns:
        The minimum number of coins, or -1.

    Example:
        >>> coin_change([1, 3, 4], 6)
        2
    """
    # Any real answer uses at most `amount` coins (all of value 1), so
    # amount + 1 is unreachable and makes a clean finite sentinel.
    unreachable = amount + 1
    best = [unreachable] * (amount + 1)
    best[0] = 0

    for value in range(1, amount + 1):
        for coin in coins:
            if coin <= value:
                best[value] = min(best[value], best[value - coin] + 1)

    return -1 if best[amount] == unreachable else best[amount]

Walkthrough

coins = [1, 3, 4], amount = 6:

The winner at v = 6 comes through the 3-coin, which is exactly the case greedy misses.

The sibling: counting combinations

def coin_change_ways(coins: list[int], amount: int) -> int:
    """Coin Change II: how many distinct combinations sum to amount."""
    ways = [0] * (amount + 1)
    ways[0] = 1                      # one way to make zero: take nothing

    # Coins on the OUTSIDE loop. This fixes an order on the coins, so
    # 1+3 and 3+1 are counted once. Swapping the loops counts permutations.
    for coin in coins:
        for value in range(coin, amount + 1):
            ways[value] += ways[value - coin]

    return ways[amount]

Edge cases to raise

• amount == 0: returns 0, from the base case.
• No combination works, such as coins = [2] with amount = 3: returns -1.
• A coin larger than the amount: skipped by the coin <= value guard.
• Empty coin list with a positive amount: returns -1.
• Using float("inf") instead of the sentinel also works, but then inf + 1 appears in the arithmetic. The finite sentinel avoids that entirely.

3. Longest Increasing Subsequence Medium

Problem

Return the length of the longest strictly increasing subsequence of an array. A subsequence may skip elements but must keep the original order.

The state that does not work, and the one that does

The five questions

1. State: best[i] = LIS length ending exactly at i.
2. Recurrence: best[i] = 1 + max(best[j]) over all j < i with nums[j] < nums[i].
3. Base: best[i] = 1. Every element alone is a subsequence of length one.
4. Order: increasing i.
5. Answer: max(best), not best[-1], because the best subsequence need not end at the last element.

Solution: O(n²)

def length_of_lis(nums: list[int]) -> int:
    """Length of the longest strictly increasing subsequence.

    Args:
        nums: Integers, in any order.

    Returns:
        The length of the longest strictly increasing subsequence.

    Example:
        >>> length_of_lis([10, 9, 2, 5, 3, 7, 101, 18])
        4
    """
    if not nums:
        return 0

    # best[i] is the LIS length ending exactly at index i.
    best = [1] * len(nums)

    for i in range(1, len(nums)):
        for j in range(i):
            if nums[j] < nums[i]:
                best[i] = max(best[i], best[j] + 1)

    # The optimum can end anywhere, so take the maximum over all endings.
    return max(best)

Solution: O(n log n), patience sorting

import bisect


def length_of_lis_fast(nums: list[int]) -> int:
    """Same answer in O(n log n) by keeping the best tail for each length.

    tails[k] is the smallest possible final value of any increasing
    subsequence of length k + 1 seen so far. It is sorted by construction,
    so each element can be placed with a binary search.
    """
    tails: list[int] = []

    for value in nums:
        index = bisect.bisect_left(tails, value)

        if index == len(tails):
            tails.append(value)      # extends the longest run found so far
        else:
            tails[index] = value     # a smaller tail for that length: strictly better

    return len(tails)

Walkthrough of the fast version

nums = [10, 9, 2, 5, 3, 7, 101, 18]:

Length 4. Notice [2, 3, 7, 18] happens to be a real subsequence here, but that is a coincidence, not a guarantee.

Edge cases to raise

• Empty array: 0. The max() in the DP version would raise on an empty list, hence the guard.
• Strictly decreasing input: answer 1.
• All equal: answer 1, because the requirement is strictly increasing.
• Non-decreasing allowed instead: switch bisect_left to bisect_right in the fast version, and < to <= in the DP. One-character changes, worth flagging.
• Reconstructing the actual subsequence needs a parent-pointer array; the fast version makes that noticeably harder. Mention it if asked.

4. 0/1 Knapsack Medium

Problem

Each item has a weight and a value. Choose a subset with total weight at most capacity that maximises total value. Each item may be taken at most once, which is the “0/1”.

The five questions

1. State: best[i][w] is the maximum value using only the first i items within weight budget w.
2. Recurrence: for item i there are exactly two options, skip it or take it:
   best[i][w] = max(best[i-1][w], best[i-1][w - weight[i]] + value[i]), the second only when it fits.
3. Base: best[0][w] = 0. No items, no value.
4. Order: items outer, capacities inner.
5. Answer: best[n][capacity].

Solution: 2D table

def knapsack_2d(weights: list[int], values: list[int], capacity: int) -> int:
    """Maximum value from a subset of items fitting inside capacity.

    Args:
        weights: Positive item weights.
        values: Item values, same length as weights.
        capacity: Maximum total weight, capacity >= 0.

    Returns:
        The best achievable total value.

    Raises:
        ValueError: If weights and values have different lengths.

    Example:
        >>> knapsack_2d([1, 3, 4, 5], [1, 4, 5, 7], 7)
        9
    """
    if len(weights) != len(values):
        raise ValueError("weights and values must have the same length")

    n = len(weights)
    # A comprehension, NOT [[0] * m] * n, which aliases one row n times.
    best = [[0] * (capacity + 1) for _ in range(n + 1)]

    for i in range(1, n + 1):
        weight, value = weights[i - 1], values[i - 1]

        for room in range(capacity + 1):
            skip = best[i - 1][room]

            if weight <= room:
                take = best[i - 1][room - weight] + value
                best[i][room] = max(skip, take)
            else:
                best[i][room] = skip

    return best[n][capacity]

Solution: one row, and the direction that matters

def knapsack(weights: list[int], values: list[int], capacity: int) -> int:
    """Same answer in O(capacity) space.

    Row i depends only on row i - 1, so one array suffices. The inner loop
    must run BACKWARDS: it guarantees that best[room - weight] still holds
    the previous item's value, which is what enforces "each item at most once".
    """
    best = [0] * (capacity + 1)

    for weight, value in zip(weights, values):
        for room in range(capacity, weight - 1, -1):
            best[room] = max(best[room], best[room - weight] + value)

    return best[capacity]

Walkthrough

weights = [1, 3, 4, 5], values = [1, 4, 5, 7], capacity = 7. The optimum takes items 2 and 3, weights 3 + 4 = 7 and values 4 + 5 = 9. Taking item 4 alone gives 7; items 1 and 4 give 1 + 7 = 8 at weight 6. So the answer is 9.

The family this unlocks

Edge cases to raise

• capacity == 0: returns 0.
• No items: returns 0.
• An item heavier than the capacity: the range bound skips it entirely.
• Zero-weight items with positive value: always taken, and safe here. Worth confirming they can occur.
• To recover which items were chosen you need the full 2D table and a backward walk. The compressed version cannot reconstruct the set. Say so if the problem asks for the items.