The Dynamic Programming Course
Dynamic programming, one small step at a time
This course is for anyone, including people who have never written a line of code. Dynamic programming has a scary name and a simple heart. You will meet the idea in plain words, then climb four problems in order, watching each one build its answer cell by cell. No prior algorithms needed. Bring patience and a willingness to press play.
The Core Idea
Solve each small piece once, then reuse it
Picture a cook with a notepad. Every time they finish a sauce, they write it down. When a later dish needs that sauce, they read the notepad instead of making it again. Dynamic programming is exactly that habit, applied to problems: break a big question into smaller versions of itself, solve each small version once, write the answer down, and reuse it forever after.
Break it down
A big question is usually made of smaller copies of the same question. The answer for 10 stairs leans on the answer for 9 and 8.
Write each answer down
Keep a row of boxes, one per small version. Fill the easiest boxes first, then use them to fill the harder ones.
Never redo work
Once a box has a number, it is final. Every later box just reads the boxes it needs. That reuse is the whole speed-up.
The Setup
Four questions that unlock any DP problem
You do not start by writing code. You start by answering these four questions in plain words. Every problem in this course is just these four answers, filled in. The first one matters most: if you cannot say what a saved answer means, nothing after it will make sense.
What does each saved answer mean?
Finish this sentence out loud before anything else: dp[i] is the ___. The number of ways to reach stair i. The cheapest cost to reach it. The best haul up to house i.
What is the choice at each step?
Are you counting every route (add), paying for one (keep the min), or picking items (keep the max)? The choice decides whether you add, min, or max.
How does a bigger answer use smaller ones?
This is the recurrence: one short line saying how dp[i] is built from earlier boxes like dp[i-1] and dp[i-2].
Which cases can you fill in directly?
The base cases: the first box or two that you know without any formula. Get these right first, then let the recurrence handle the rest.
The Path
Four levels, each adding exactly one idea
Climb in order. The first three problems share the same picture, a single row of boxes filled left to right, and change only one thing each time: first you add, then you keep the cheaper, then you keep the better. The fourth turns that row into a grid. By the end, the grid problem that looked hard on day one reads as one more small step.
Common Traps
Three habits that prevent most beginner mistakes
Say what the box means, in words
Most stuck moments trace back to a fuzzy state. Write one plain sentence for dp[i] before you write any formula.
Get the base cases right first
The easy first boxes are where quiet bugs hide. Fill and hand-check them before trusting the recurrence.
Do not shrink memory too early
Get the full row of boxes correct first. Compressing it down to two variables is a separate, later step.
You are not here to memorize templates.
A memorized template breaks the moment a problem is twisted. The four questions do not. Once naming the state and the choice feels natural, dynamic programming stops being a category of scary problems and becomes a habit you carry into new ones. When you are ready, read the solving tips for the wider habits, or browse the Dynamic Programming field guide.