Dynamic Programming Essentials

Recursion, but with memory

Now that you have covered Recursive Algorithms and Backtracking and practiced traversing trees/graphs, you are ready for one of the biggest medium-problem unlocks: dynamic programming, usually called DP.

DP is not a totally new universe. It is a strategy for problems where:

1. You can break the problem into smaller subproblems.
2. The same smaller subproblems appear again and again.
3. You can store answers so you do not recompute them.

In a 30-day crash course, DP matters because it turns many scary-looking problems into a repeatable checklist: define the state, write the recurrence, handle base cases, and compute in a safe order.

When should you suspect DP?

DP usually appears when a problem asks for an optimal value, a count, or a yes/no possibility across many choices.

Common wording clues:

• minimum number of steps
• maximum profit or score
• number of ways
• can you reach, form, or partition something?
• choose or skip items

The deeper clue is overlap. If solving the big problem causes you to solve the same smaller problem multiple times, caching can help.

Example mental model:

fib(5)
├─ fib(4)
│  ├─ fib(3)
│  └─ fib(2)
└─ fib(3)   <- repeated

In plain recursion, fib(3) gets recomputed. In DP, we compute it once and reuse the saved answer.

Which problem description most strongly suggests dynamic programming?

Top-down DP

Memoization means writing a recursive solution, then adding a cache so each subproblem is solved once.

This style feels natural right after learning recursion:

1. Write the recursive meaning.
2. Add base cases.
3. Before doing work, check whether the answer is already cached.
4. Store the answer before returning.

Here is Fibonacci with memoization. The goal is not that Fibonacci itself is important; it is the pattern.

```python
def fib(n, memo=None):
    if memo is None:
        memo = {}

    if n in memo:
        return memo[n]

    if n <= 1:
        return n

    memo[n] = fib(n - 1, memo) + fib(n - 2, memo)
    return memo[n]

for n in range(8):
    print(f'fib({n}) = {fib(n)}')

print('fib(35) =', fib(35))
```

True or false: Memoization automatically makes every recursive algorithm fast.

Bottom-up DP

Tabulation builds answers from the smallest cases upward, usually in a list or table.

Instead of asking recursively, what is the answer for n?, we say:

• I know the smallest answers.
• I will fill larger answers in an order where dependencies are already known.

For climbing stairs, if you can take 1 or 2 steps:

ways[i] = ways[i - 1] + ways[i - 2]

Because to land on step i, your previous position was either i - 1 or i - 2.

```python
def climb_stairs(n):
    if n <= 1:
        return 1

    ways = [0] * (n + 1)
    ways[0] = 1
    ways[1] = 1

    for i in range(2, n + 1):
        ways[i] = ways[i - 1] + ways[i - 2]

    print('DP table:', ways)
    return ways[n]

print('ways to climb 5 steps =', climb_stairs(5))
print('ways to climb 10 steps =', climb_stairs(10))
```

The top-down dynamic programming technique that stores recursive subproblem results in a cache is called ______.

The DP checklist

Most DP problems become less mysterious when you name three things.

1. State

What does one subproblem represent?

Examples:

• dp[i] = answer using the first i items
• dp[i] = best answer ending at index i
• dp[r][c] = answer for cell (r, c)

2. Transition

How do smaller states combine into this state?

Examples:

• dp[i] = dp[i - 1] + dp[i - 2]
• dp[i] = max(take_current, skip_current)

3. Base cases

What tiny answers are known without more work?

If you get stuck, write a few tiny examples by hand. DP often reveals itself when you notice the same answer being reused.

A classic choose-or-skip problem

The House Robber pattern is a common medium-style DP problem:

You have a row of houses with money. You cannot rob adjacent houses. What is the maximum money you can rob?

At each house, you make a choice:

• skip it: keep the best total from the previous house
• take it: add this house to the best total from two houses back

So the transition is:

dp[i] = max(dp[i - 1], nums[i] + dp[i - 2])

This is the same DP checklist: state, transition, base cases.

```python
def rob(nums):
    if not nums:
        return 0
    if len(nums) == 1:
        return nums[0]

    dp = [0] * len(nums)
    dp[0] = nums[0]
    dp[1] = max(nums[0], nums[1])

    for i in range(2, len(nums)):
        skip_current = dp[i - 1]
        take_current = nums[i] + dp[i - 2]
        dp[i] = max(skip_current, take_current)

    print('houses:', nums)
    print('dp:', dp)
    return dp[-1]

print('max robbed =', rob([2, 7, 9, 3, 1]))
print('max robbed =', rob([1, 2, 3, 1]))
```

What to practice today

Dynamic programming is a pattern-recognition skill. The first goal is not speed; it is learning to ask the right questions.

Your DP checklist

When you see a possible DP problem, ask:

1. What is the state?
2. What smaller states does it depend on?
3. What are the base cases?
4. Do I want top-down memoization or bottom-up tabulation?
5. What is the time and space complexity?

Starter rotation

For the 2-day revisit habit in this crash course, add these to your practice queue:

• Fibonacci with memoization
• Climbing Stairs
• House Robber
• Min Cost Climbing Stairs
• Unique Paths on a grid

Revisit them every two days until the state and transition feel automatic. Next, you will compare this with Greedy Algorithms and Their Applications, where some problems can be solved by making a locally best choice instead of storing many subproblem answers.