Introduction to Dynamic Programming

Why this lesson matters

Dynamic Programming, or DP, is one of those techniques that can feel like a secret power-up: the same problem that looks impossible recursively can become efficient once you notice repeated work.

In this first lesson, we’ll build the mental model:

• What DP is
• When a problem is a good DP candidate
• Why caching previous answers changes performance
• How Python lets us express DP cleanly

Think of DP like a strategist in an anime tournament arc: instead of re-fighting the same battle every episode, we remember the outcome and move forward smarter.

Dynamic Programming in one sentence

Dynamic Programming solves problems by breaking them into smaller overlapping subproblems, storing their answers, and reusing those answers instead of recomputing them.

A problem is usually DP-friendly when it has two properties:

1. Overlapping subproblems

The same smaller questions appear again and again.

Example idea:

solve(A) needs solve(B) and solve(C)
solve(B) also needs solve(C)

If solve(C) is expensive, computing it twice is wasteful.

2. Optimal substructure

The best answer to the big problem can be built from best answers to smaller problems.

In manga terms: if a hero’s final strategy depends on mastering smaller techniques, and those techniques can be reused across fights, you have a DP-shaped story.

Which situation is the strongest sign that Dynamic Programming might be useful?

The hidden cost of recursion

Recursive thinking is often the first step toward DP. You define a problem in terms of smaller versions of itself.

But plain recursion can create a branching tree where the same state appears multiple times.

                solve(5)
              /          \
         solve(4)        solve(3)
         /     \         /     \
    solve(3) solve(2) solve(2) solve(1)

Notice how solve(3) and solve(2) appear more than once.

DP says: once we solve a state, archive it like an important flashback scene. When it appears again, reuse it instantly.

A tiny optimization problem

Suppose a character travels across checkpoints. From checkpoint i, they may move 1 or 2 steps forward. Each checkpoint has a cost, and we want the minimum total cost to reach the final checkpoint.

Here is a direct recursive version. It is readable, but it recomputes the same positions multiple times.

```python
costs = [4, 2, 7, 1, 3]
call_count = 0


def min_cost_from(i):
    global call_count
    call_count += 1

    if i >= len(costs):
        return 0

    take_one = min_cost_from(i + 1)
    take_two = min_cost_from(i + 2)
    return costs[i] + min(take_one, take_two)


answer = min_cost_from(0)
print("Minimum cost:", answer)
print("Recursive calls:", call_count)
```

Top-down DP

The first common DP style is memoization, also called top-down DP.

We keep the recursive structure, but add a dictionary:

• Key: a subproblem state, such as i
• Value: the answer for that state

Before solving a state, we check whether it is already cached. If yes, we return the stored answer immediately.

```python
costs = [4, 2, 7, 1, 3]
cache = {}
call_count = 0


def min_cost_from(i):
    global call_count
    call_count += 1

    if i >= len(costs):
        return 0

    if i in cache:
        return cache[i]

    take_one = min_cost_from(i + 1)
    take_two = min_cost_from(i + 2)
    cache[i] = costs[i] + min(take_one, take_two)
    return cache[i]


answer = min_cost_from(0)
print("Minimum cost:", answer)
print("Function calls:", call_count)
print("Cached states:", cache)
```

True or false: Dynamic Programming means storing answers to useful repeated subproblems, not necessarily storing every possible value in the universe of inputs.

Bottom-up DP

The second common DP style is tabulation, also called bottom-up DP.

Instead of starting from the big question and recursing downward, we build answers from small states upward.

For the checkpoint problem, we can compute from the end backward:

dp[i] = minimum cost to finish starting at checkpoint i

This avoids recursion entirely.

```python
costs = [4, 2, 7, 1, 3]
n = len(costs)

# Extra two positions represent "already past the end" with cost 0.
dp = [0] * (n + 2)

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

print("Minimum cost:", dp[0])
print("DP table:", dp)
```

The smaller reusable questions that a DP solution solves are called overlapping ____.

A practical checklist

When you face a new algorithm problem, ask:

1. Can I describe the answer recursively?
2. Do the same states repeat?
3. Can a state be represented compactly?
   • index
   • pair of indices
   • capacity remaining
   • interval boundaries
4. Can I define a recurrence?
   • current answer from smaller answers
5. What should I store?
   • dictionary cache
   • list/table
   • 2D grid

In upcoming lessons, we’ll apply these ideas to classic DP patterns, starting with a simple sequence problem and then moving into strings, choices, and intervals.