One-Dimensional DP

Define the state in words

Dynamic programming applies when a problem has overlapping subproblems and optimal substructure. Define the state in words ("dp[a] is the fewest coins making amount a"), the transition (dp[a] = min(dp[a - c] + 1)), and base cases (dp[0] = 0). Solve top-down with memoisation (functools.lru_cache) or bottom-up with a table; often only the last few states are needed, reducing space to O(1).

Reuse subproblems, explore choices

Dynamic programming reuses overlapping subproblems; backtracking explores choices and undoes them.

House robber, coin change and memoised stairs, run

I ran this with Python 3.12.3 (standard library only). Robbing houses 2, 9 and 1 gives 12; 11 needs 3 coins (5+5+1) and 3 cannot be made from 2s; for coins 1, 3 and 4, amount 6 needs 2 coins (3+3), where a greedy choice of 4 first would need 3; memoisation makes climb(50) instant.

# 1-D dynamic programming: house robber and coin change
from functools import lru_cache

def rob(houses):
    take, skip = 0, 0                     # best ending with / without robbing the last house
    for h in houses:
        take, skip = skip + h, max(take, skip)
    return max(take, skip)

def coin_change(coins, amount):
    INF = amount + 1
    dp = [0] + [INF] * amount             # dp[a] = fewest coins to make a
    for a in range(1, amount + 1):
        for c in coins:
            if c <= a:
                dp[a] = min(dp[a], dp[a - c] + 1)
    return dp[amount] if dp[amount] != INF else -1

@lru_cache(maxsize=None)
def climb(n):                             # top-down memoisation
    return 1 if n <= 1 else climb(n - 1) + climb(n - 2)

print(rob([2, 7, 9, 3, 1]), rob([2, 1, 1, 2]))
print(coin_change([1, 2, 5], 11), coin_change([2], 3), coin_change([1, 3, 4], 6))
print(climb(10), climb(50))

Output:

12 4
3 -1 2
89 20365011074

Start with recursion plus memo

Writing the recursive relation first and adding lru_cache is often the fastest way to a correct DP in an interview.

Quick check: Why does greedy fail for coin change with coins [1, 3, 4] and amount 6?

• Taking 4 first leads to 4+1+1 (3 coins) while 3+3 needs only 2
• Greedy always succeeds
• Amount 6 cannot be made
• Coins must be sorted descending