“Just use DP!” “Wait, what?” -Me in COMP2823"

The Core Idea #

Dynamic programming = solve a problem once, save the answer, reuse it later.

If a problem breaks into smaller pieces, and those pieces repeat, DP helps by remembering.

Example: Climbing Stairs (ELI5) #

Imagine you can take either 1 step or 2 steps at a time.

If you want to reach the 4th step, you have a few options:

• Step 1 → Step 2 → Step 3 → Step 4
• Step 1 → Step 3 → Step 4
• Step 2 → Step 3 → Step 4
• Step 2 → Step 4
• and so on…

You might notice that to get to step 4, you must come from step 3 or step 2.

So we can say:

ways(4) = ways(3) + ways(2)

If we draw it as a tree, it looks like this:

        ways(4)
       /      \
   ways(3)   ways(2)
   /    \      /   \
ways(2) ways(1) ways(1) ways(0)

See how ways(2) and ways(1) repeat?

That’s where dynamic programming helps. We save answers we’ve already seen so we don’t redo the same work.

Instead of solving top-down again and again, we just fill the answers bottom-up starting from:

ways(0),ways(1) = 1
(As there is only one way at that point!)

and work our way up to ways(4).

The hard part is just seeing how the big problem breaks into smaller ones. The code part is often easy once you get that.

When to DP #

• You keep solving the same subproblem
• Brute force would repeat work
• There is a clear relationship between subproblems