Practice Problems

These five problems were written for this guide. Try each one before reading the approach: write down the state, the recurrence, the base cases and the order first, then code it. All solutions run with Python 3.9 or later.

Problem 1: stairs with broken steps

A staircase has n steps. You start on step 0 and may climb 1, 2 or 3 steps at a time, but some steps are broken and cannot be stepped on. How many different ways are there to reach step n? Return the count modulo 1_000_000_007.

Example: with n = 4 and step 2 broken, the valid routes are 0-1-4, 0-3-4 and 0-1-3-4, so the answer is 3. Routes such as 0-2-4 or 0-1-2-3-4 are invalid because they touch step 2.

Approach: ways[i] = number of ways to stand on step i. Broken steps have 0 ways; otherwise ways[i] = ways[i-1] + ways[i-2] + ways[i-3]. Base case ways[0] = 1.

MOD = 1_000_000_007


def count_climbs(n: int, broken: set[int]) -> int:
    ways = [0] * (n + 1)
    ways[0] = 1
    for i in range(1, n + 1):
        if i in broken:
            continue
        ways[i] = sum(ways[i - s] for s in (1, 2, 3) if i - s >= 0) % MOD
    return ways[n]


print(count_climbs(4, {2}))  # 3
print(count_climbs(30, set()))  # 53798080

Problem 2: cheapest route across a grid

A warehouse floor is a grid of tolls. A robot starts at the top-left cell and must reach the bottom-right cell, moving only right or down, paying the toll of every cell it enters (including the first). Find the minimum total toll.

Approach: cost[r][c] = cheapest total to arrive at cell (r, c). Each cell is reached from above or from the left, so cost[r][c] = grid[r][c] + min(above, left). A single row suffices because each row only needs the row above.

def cheapest_route(grid: list[list[int]]) -> int:
    cols = len(grid[0])
    row = [0] * cols
    for r, line in enumerate(grid):
        for c, toll in enumerate(line):
            if r == 0 and c == 0:
                row[c] = toll
            elif r == 0:
                row[c] = row[c - 1] + toll
            elif c == 0:
                row[c] = row[c] + toll
            else:
                row[c] = min(row[c], row[c - 1]) + toll
    return row[-1]


print(cheapest_route([[1, 3, 1], [1, 5, 1], [4, 2, 1]]))  # 7

Problem 3: typo distance

A search box wants to suggest the closest product name to what a user typed. Define the distance between two words as the fewest single-character insertions, deletions or substitutions needed to turn one into the other (Levenshtein distance). Compute it.

Approach: d[i][j] = distance between the first i characters of s and the first j of t. If the characters match, d[i][j] = d[i-1][j-1]; otherwise it is 1 plus the minimum of delete (d[i-1][j]), insert (d[i][j-1]) and substitute (d[i-1][j-1]). Base cases: d[i][0] = i, d[0][j] = j.

def edit_distance(s: str, t: str) -> int:
    prev = list(range(len(t) + 1))
    for i, a in enumerate(s, start=1):
        cur = [i] + [0] * len(t)
        for j, b in enumerate(t, start=1):
            if a == b:
                cur[j] = prev[j - 1]
            else:
                cur[j] = 1 + min(prev[j], cur[j - 1], prev[j - 1])
        prev = cur
    return prev[-1]


print(edit_distance("keybaord", "keyboard"))  # 2
print(edit_distance("kitten", "sitting"))    # 3

Problem 4: fair split of a prize pool

A team won several prizes with integer values. Can they be divided into two groups with exactly equal total value?

Approach: if the total is odd, the answer is no. Otherwise ask whether some subset sums to total // 2. That is a 0/1 knapsack with booleans: can[s] is true when some subset of the items seen so far sums to s. Iterate sums from high to low so each prize is used once.

def can_split_evenly(prizes: list[int]) -> bool:
    total = sum(prizes)
    if total % 2:
        return False
    target = total // 2
    can = [True] + [False] * target
    for p in prizes:
        for s in range(target, p - 1, -1):
            can[s] = can[s] or can[s - p]
    return can[target]


print(can_split_evenly([3, 1, 5, 9, 4]))  # False (total 22, no subset sums to 11)
print(can_split_evenly([3, 1, 5, 9, 2]))  # True (9 + 1 = 3 + 5 + 2)

Problem 5: longest warming streak

Given daily temperatures, find the longest sequence of days (not necessarily consecutive) on which each day was strictly warmer than the previous chosen day, and return one such sequence.

Approach: the O(n^2) LIS is easy to reconstruct. length[i] is the longest increasing subsequence ending at day i, and parent[i] remembers the previous day in that subsequence.

def warming_streak(temps: list[int]) -> list[int]:
    if not temps:
        return []
    n = len(temps)
    length = [1] * n
    parent = [-1] * n
    for i in range(n):
        for j in range(i):
            if temps[j] < temps[i] and length[j] + 1 > length[i]:
                length[i] = length[j] + 1
                parent[i] = j
    i = max(range(n), key=length.__getitem__)
    streak = []
    while i != -1:
        streak.append(temps[i])
        i = parent[i]
    return streak[::-1]


print(warming_streak([12, 9, 14, 10, 15, 11, 18, 13]))  # [12, 14, 15, 18]

For long inputs, combine the bisect version from the complexity chapter with an index array to reconstruct in O(n log n).

Summary

• Counting problems add over choices; optimization problems take a min or max.
• Grid and string problems use two indices, but often need only one row of memory.
• Many "is it possible" questions reduce to a boolean knapsack.
• Store a parent pointer whenever you must output the solution, not just its size.