# Dynamic Programming Fundamentals — Part 1: The Pattern

Dynamic programming solves problems whose brute force recomputes the **same subproblems** again and again. You define the answer for a smaller **state**, express it through even smaller states (the **transition**), and store each result so it's computed once. Exponential recursion becomes polynomial. DP feels hard mostly because people skip the definition step; with a fixed recipe it becomes mechanical.

![A DP table filled left to right from base cases](diagrams/01-dp-table.svg)

## 1. When Is It DP?

Two properties:

1. **Optimal substructure:** the best answer for the whole problem is built from best answers to subproblems.
2. **Overlapping subproblems:** the recursion tree solves the same subproblem many times (Fibonacci's `f(3)` appears repeatedly).

Wording cues: "number of ways", "minimum/maximum cost", "longest/shortest … subsequence", "can you reach/form …", choices at each step that affect future options.

## 2. The Five-Step Recipe

1. **State:** what does `dp[i]` (or `dp[i][j]`) mean, in one sentence? ("number of ways to reach step i")
2. **Transition:** how is `dp[i]` computed from smaller states? (`dp[i] = dp[i−1] + dp[i−2]`)
3. **Base cases:** the smallest states with known answers (`dp[0] = dp[1] = 1`).
4. **Order:** compute states so dependencies are ready (increasing i).
5. **Answer:** which state is the final answer (`dp[n]`), and can you reduce space?

## 3. Top-Down vs Bottom-Up

```typescript
function climbMemo(n: number, memo = new Map<number, number>()): number {
  if (n <= 1) return 1;
  if (memo.has(n)) return memo.get(n)!;
  const v = climbMemo(n - 1, memo) + climbMemo(n - 2, memo);
  memo.set(n, v);
  return v;
}

function climbTable(n: number): number {
  const dp = new Array(n + 1).fill(1);
  for (let i = 2; i <= n; i++) dp[i] = dp[i - 1] + dp[i - 2];
  return dp[n];
}

function climbO1(n: number): number {
  let a = 1, b = 1;
  for (let i = 1; i < n; i++) [a, b] = [b, a + b];
  return b;
}

function climbBoth(n: number): number[] {
  return [climbMemo(n), climbTable(n), climbO1(n)];
}
```

```python
from functools import lru_cache

def climb_memo(n):                          # top-down: recursion + cache
    @lru_cache(maxsize=None)
    def f(i):
        if i <= 1:
            return 1                        # base cases
        return f(i - 1) + f(i - 2)          # transition
    return f(n)

def climb_table(n):                         # bottom-up: fill a table in order
    dp = [1] * (n + 1)
    for i in range(2, n + 1):
        dp[i] = dp[i - 1] + dp[i - 2]
    return dp[n]

def climb_o1(n):                            # space-optimized: keep only what's needed
    a, b = 1, 1
    for _ in range(n - 1):
        a, b = b, a + b
    return b

def climb_both(n):
    return [climb_memo(n), climb_table(n), climb_o1(n)]
```

| | Top-down (memoized recursion) | Bottom-up (tabulation) |
|---|---|---|
| writing it | natural from the recurrence | needs an explicit order |
| computes | only reachable states | every state |
| risk | recursion depth limits (Python ~1,000) | none |
| space optimization | hard | easy: keep only the last row(s) |

A good interview flow: write the recurrence, code top-down quickly, then convert to bottom-up with O(1) or O(n) space if asked.

## 4. Common 1D DP Families

| Family | State | Transition |
|---|---|---|
| counting paths (stairs, decode ways) | ways to reach i | sum over the last step choices |
| take / skip (house robber) | best up to i | `max(skip: dp[i−1], take: dp[i−2] + a[i])` |
| unbounded choices (coin change) | best for amount a | `min over coins c: dp[a − c] + 1` |
| subsequence ending at i (LIS) | best ending exactly at i | max over earlier j that can precede i |
| segmentation (word break) | can prefix of length i be built? | any j with dp[j] and s[j:i] a word |

## Under the Hood: Why Memoization Changes Complexity

Complexity of a DP = **(number of distinct states) × (work per state)**. Naive Fibonacci makes ~2ⁿ calls but has only n distinct states; with a cache each state is computed once, so it's O(n). Coin change has `amount` states × `len(coins)` choices = O(amount · k). Always state complexity in this form. Interviewers like hearing that you know where it comes from.

## Common Pitfalls

1. **Vague state definitions** ("dp[i] is the answer for i"): say exactly what it represents, including whether i is *included* or *ending at*.
2. **Wrong base cases** (`dp[0]` for "zero amount needs zero coins", "empty string decodes in one way").
3. **Iterating in the wrong order** so `dp[i]` reads values not yet computed.
4. **Using greedy** where choices interact (coin change).
5. **Forgetting impossibility markers** (`inf` for unreachable amounts, then mapping back to −1).

## Quick Reference

```text
Recipe: state → transition → base → order → answer (→ shrink space)
Complexity = #states × work per state
take/skip: dp[i] = max(dp[i-1], dp[i-2] + a[i])
unbounded: dp[a] = min(dp[a-c] + 1 for c in coins)
top-down = recursion + cache · bottom-up = table in dependency order
```