# One-Dimensional DP — DSA Interview Patterns

Source: https://www.skillbyai.com/en/dsa-interview-patterns/d-1d

> State, transition, base case.

## 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.

![Four ideas: 1-D DP, 2-D DP, backtracking, interview checklist.](assets/figures/dsa-interview-patterns/section-8-map.svg) — Figure 8.1 — 1-D DP, 2-D DP and backtracking.

## 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.

```python
# 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.

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

- [x] 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

*Answer:* Taking 4 first leads to 4+1+1 (3 coins) while 3+3 needs only 2. DP considers all choices.