Dynamic Programming Essentials

Dynamic Programming is recursion with a memory

Now that you've covered Mastering Recursion and Divide and Conquer Strategies, you're ready for the next upgrade: solving repeated subproblems only once.

In recursion, we often ask: “What is the answer for a smaller version of this problem?”

In dynamic programming, we add: “Have I already solved that smaller version?”

DP matters in interviews because many easy/medium problems hide the same pattern:

• Count the number of ways
• Find the best/min/max value
• Decide whether something is possible
• Build an answer from earlier answers

Today’s goal: learn the core DP workflow, not memorize 50 formulas.

The core idea

Dynamic programming is useful when a problem has:

1. Overlapping subproblems

The same smaller questions appear again and again.

Example: fib(5) needs fib(4) and fib(3). But fib(4) also needs fib(3).

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

2. Optimal substructure

The answer can be built from correct answers to smaller subproblems.

For example, if the best answer for step i depends on the best answers for earlier steps, DP may fit.

A simple DP question to ask yourself:

“If I knew the answer for smaller positions, could I compute the answer for this position?”

Which problem description is the strongest signal that dynamic programming might help?

Top-down DP

The beginner-friendly way to enter DP is memoization:

1. Write the recursive solution.
2. Store answers in a dictionary.
3. Before solving a subproblem, check whether it is already stored.

This is called top-down because you start from the big question and recursively ask smaller questions.

For Fibonacci, the recurrence is:

fib(n) = fib(n - 1) + fib(n - 2)

Without memory, recursion repeats work. With memory, each n is solved once.

```python
# Top-down dynamic programming: memoized Fibonacci

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 i in range(8):
    print(i, fib(i))
```

True or false: memoization can turn some recursive solutions from exponential time into much faster solutions by avoiding repeated subproblems.

The most important DP skill

Before coding, define the state.

A state is a precise meaning for one DP entry.

Examples:

• dp[i] = number of ways to reach step i
• dp[i] = minimum cost to reach step i
• dp[i] = best score considering houses up to index i

Then define the transition:

How do earlier states create the current state?

For climbing stairs where you can move 1 or 2 steps:

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

Why? Every path to step i must come from either step i - 1 or step i - 2.

This is where your recursion training pays off: the recurrence is the same idea, but now we store results deliberately.

In the climbing stairs problem, if each move can be 1 or 2 steps, complete the recurrence:

ways(i) = ____

Bottom-up DP

Tabulation solves smaller states first, usually in a loop.

This is called bottom-up because you build from base cases toward the final answer.

Use tabulation when:

• The order of states is clear
• You want to avoid recursion depth issues
• The recurrence naturally moves left to right

Example problem: minimum cost climbing stairs.

You can start at step 0 or step 1. Each time, climb 1 or 2 steps. Pay the cost of the step you land on. Find the minimum cost to reach the top.

```python
# Bottom-up dynamic programming: minimum cost climbing stairs

def min_cost_climbing_stairs(cost):
    n = len(cost)
    dp = [0] * (n + 1)

    # dp[i] = minimum cost to reach position i
    # Position n means the top, beyond the last step.
    for i in range(2, n + 1):
        one_step = dp[i - 1] + cost[i - 1]
        two_steps = dp[i - 2] + cost[i - 2]
        dp[i] = min(one_step, two_steps)

    print("dp table:", dp)
    return dp[n]

print(min_cost_climbing_stairs([10, 15, 20]))
print(min_cost_climbing_stairs([1, 100, 1, 1, 1, 100, 1, 1, 100, 1]))
```

Do you need the whole table?

Often, a DP recurrence only depends on the last one or two states.

If so, you can compress space:

Full table:  dp[0], dp[1], dp[2], ..., dp[n]
Compressed:  previous, current

Example: House Robber.

You have a row of houses. Each house has money. You cannot rob adjacent houses. Return the maximum money possible.

State idea:

best up to this house = max(
  skip this house,
  rob this house + best before previous house
)

This is a great medium-style DP pattern: at each position, choose between taking and skipping.

```python
# Space-optimized DP: House Robber

def rob(nums):
    two_back = 0  # best before the previous house
    one_back = 0  # best up to the previous house

    for money in nums:
        take = money + two_back
        skip = one_back
        current = max(take, skip)

        two_back = one_back
        one_back = current

    return one_back

print(rob([1, 2, 3, 1]))      # 4
print(rob([2, 7, 9, 3, 1]))   # 12
```

Your DP checklist

When you see a possible DP problem, walk through this checklist:

1. What is the state?

   • What does dp[i] mean?

2. What are the base cases?

   • What answers are immediately known?

3. What is the transition?

   • How do smaller answers create the current answer?

4. What order should I compute states?

   • Top-down memoization or bottom-up tabulation?

5. Can space be reduced?

   • Do you need the whole table, or only recent values?

Two-day drill

To match this crash course’s review rhythm, revisit these every 2 days:

• Fibonacci with memoization
• Climbing stairs
• Minimum cost climbing stairs
• House robber

Next, you’ll focus on turning this review loop into a repeatable habit so these patterns stick under pressure.