# Dynamic Programming — Data Structures & Algorithms

Source: https://www.geekswithgeeks.com/en/dsa/dynamic-programming

> Solve overlapping subproblems once, store the answers, and build up.

## Two conditions

DP applies when a problem has (1) **optimal substructure** — the best answer is built from best answers to subproblems — and (2) **overlapping subproblems** — the same subproblem recurs. Cache each subproblem's answer so you compute it once.

## Top-down: memoisation

Write the recursion, then add a cache. Fibonacci goes from `O(2^n)` to `O(n)`.

```python
from functools import lru_cache

@lru_cache(maxsize=None)
def fib(n):
    if n < 2:
        return n
    return fib(n - 1) + fib(n - 2)
```

## Bottom-up: tabulation

Fill a table from base cases upward. Often you can keep only the last row or two — dropping space to `O(1)`.

```python
def climb_stairs(n):     # ways to climb, 1 or 2 steps
    a, b = 1, 1
    for _ in range(n):
        a, b = b, a + b
    return a
```

Output:

```
climb_stairs(5) -> 8
```

## How to approach a DP

1) Define the state (what do the indices mean?). 2) Write the transition (how does a state depend on smaller states?). 3) Set base cases. 4) Decide order of evaluation. Classics: knapsack, LCS, edit distance, coin change, LIS.