Climbing Stairs, House Robber and Min Cost
26 min · Intermediate
Need help? Ask a tutor on WhatsApp (opens in a new tab)Three small problems show most of the one-dimensional pattern. In each, the answer for position i depends on the cell right before it and the one before that.
Counting ways to climb
Counting DP finds how many ways something can be done. Each cell adds the counts of the earlier cells that can lead to it, and the base cell is usually 1.
A staircase has n steps and you climb one or two at a time. The last move came from step i - 1 or step i - 2, so the ways to reach i add up those two.
def climb(n): dp = [1, 1] + [0] * (n - 1) for i in range(2, n + 1): dp[i] = dp[i - 1] + dp[i - 2] return dp[n]
print(climb(6))Example 1 · Brute force against the table
def climb_slow(n): if n <= 1: return 1 return climb_slow(n - 1) + climb_slow(n - 2)
def climb(n): a, b = 1, 1 for _ in range(n - 1): a, b = b, a + b return b
print(climb_slow(15), climb(15))print(climb(100))987 987 573147844013817084101
What this code does
- Both agree. The recursion repeats work and is O(2^n); the loop is O(n) with two variables.
- Comparing a slow and a fast version on small input is a good way to test.
Example 2 · Steps of 1, 2 or 3
def ways(n, moves=(1, 2, 3)): dp = [1] + [0] * n for i in range(1, n + 1): dp[i] = sum(dp[i - m] for m in moves if i - m >= 0) return dp[n]
print([ways(n) for n in range(1, 9)])print(ways(10, (1, 5)))[1, 2, 4, 7, 13, 24, 44, 81] 8
What this code does
- The set of allowed moves is a parameter. Each cell sums the cells one allowed move away.
- The test
i - m >= 0stops the index from going negative, which Python would accept silently and give a wrong answer.
dp[i] is the number of ways to stand on step i. Time is O(n) and space is O(n). Python never overflows, so even climb(200) is exact.
House robber: take it or skip it
Take or skip is a transition that compares two choices for the current item and keeps the better total. It is the base of many one-dimensional DP problems.
Houses in a row hold amounts of money. You may not take from two neighbours. For house i you either skip it, keeping the best up to i - 1, or take it and add the best up to i - 2.
def rob(money): prev, best = 0, 0 for m in money: prev, best = best, max(best, prev + m) return best
print(rob([6, 2, 9, 4, 7]))Example 3 · Watch the robber table
money = [6, 2, 9, 4, 7]dp = [0, money[0]]for i in range(1, len(money)): dp.append(max(dp[i], dp[i - 1] + money[i]))print(dp)[0, 6, 6, 15, 15, 22]
What this code does
dp[k]is the best total using the first k houses. It never decreases.- The last value, 22, takes 6, 9 and 7.
Example 4 · Houses in a circle
def rob(money): prev, best = 0, 0 for m in money: prev, best = best, max(best, prev + m) return best
def rob_circle(money): if len(money) == 1: return money[0] return max(rob(money[1:]), rob(money[:-1]))
print(rob_circle([2, 3, 2]))print(rob_circle([6, 2, 9, 4, 7]))3 16
What this code does
- If the first and last house are neighbours, you cannot take both. Solve twice: without the first, and without the last.
- Slicing builds new lists, so this uses O(n) extra space. That is fine here.
best is the answer so far and prev is the answer one house earlier, so two variables are enough: O(n) time and O(1) space. The max of take and skip is the transition.
Minimum cost to climb
Each step has a price to pay when you leave it. You may start on step 0 or 1 and want to pass the last step. The cheapest way to reach a step comes from one or two steps below.
def min_cost(cost): n = len(cost) dp = [0] * (n + 1) for i in range(2, n + 1): dp[i] = min(dp[i - 1] + cost[i - 1], dp[i - 2] + cost[i - 2]) return dp[n]
print(min_cost([10, 15, 20]))Example 5 · Cheapest climb, rolling
cost = [1, 100, 1, 1, 1, 100, 1, 1, 100, 1]a = b = 0for i in range(2, len(cost) + 1): a, b = b, min(b + cost[i - 1], a + cost[i - 2])print(b)6
What this code does
aandbare the cheapest costs two and one positions back. The table shrinks to two variables.- The path skips every 100 step, so the total is 6.
dp[i] is the cheapest cost to stand on position i, where position n is just past the last step. Both starts cost 0. Time is O(n).
Rebuilding the choices
A table gives the best value, not how you got it. Walk back from the end and at each cell ask which choice produced the value. That recovers the chosen houses.
def rob_houses(money): n = len(money) dp = [0] * (n + 2) for i in range(n): dp[i + 2] = max(dp[i + 1], dp[i] + money[i]) chosen, i = [], n while i > 0: if dp[i + 1] == dp[i]: i -= 1 else: chosen.append(i - 1) i -= 2 return dp[n + 1], chosen[::-1]
print(rob_houses([6, 2, 9, 4, 7]))Example 6 · Which houses were robbed
money = [6, 2, 9, 4, 7]n = len(money)dp = [0] * (n + 2)for i in range(n): dp[i + 2] = max(dp[i + 1], dp[i] + money[i])chosen, i = [], nwhile i > 0: if dp[i + 1] == dp[i]: i -= 1 else: chosen.append(i - 1) i -= 2print(dp[n + 1], chosen[::-1])22 [0, 2, 4]
What this code does
- The value is 22 and the houses are 0, 2 and 4 (counting from 0).
- When two answers tie, either choice is valid. This walk prefers to skip.
The table is shifted by 2, so dp[i + 2] is the best for houses 0 to i. The walk back keeps the table, so space is O(n).
Next step
Check your understanding
11 quick questions