Dynamic Programming: Solving Problems by Remembering

A staircase question that seems too small to matter

You are standing at the bottom of a staircase with 5 steps, on your way up to the library. You are allowed to climb either 1 step or 2 steps at a time — never 0, never 3 or more. In how many different ways can you reach the top?

Try listing a few before reading on. You might climb 1-1-1-1-1 (five single steps). Or 2-2-1. Or 1-2-2. Or 2-1-2. Each different sequence of 1s and 2s that adds up to 5 counts as a different way, even if the total number of steps taken differs. It is easy to lose count by hand once the staircase gets past 4 or 5 steps, which is exactly the point: this "small" counting question is the cleanest possible doorway into dynamic programming (DP), a technique for solving problems that are built out of smaller copies of themselves, without wastefully solving the same smaller copy again and again.

The trick to counting the ways is to reason about the very last move you made, not the first one. Whatever sequence of steps you took, your final move onto step n was either a 1-step taken from step n - 1, or a 2-step taken from step n - 2. There is no third option. So every way of reaching step n is either "a way of reaching step n - 1, followed by one last 1-step" or "a way of reaching step n - 2, followed by one last 2-step." These two groups do not overlap — a way cannot simultaneously end in a 1-step and a 2-step — so the total count is simply the sum:

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

This single line is called a recurrence relation: it defines the answer for size n in terms of answers for smaller sizes. It needs two starting points (base cases) before it means anything: ways(0) = 1 (there is exactly one way to be already standing on a 0-step staircase — do nothing) and ways(1) = 1 (the only way to climb one step is a single 1-step).

With those three facts, you can build up the answer for any staircase by hand:

• ways(2) = ways(1) + ways(0) = 1 + 1 = 2
• ways(3) = ways(2) + ways(1) = 2 + 1 = 3
• ways(4) = ways(3) + ways(2) = 3 + 2 = 5
• ways(5) = ways(4) + ways(3) = 5 + 3 = 8

Eight ways to climb five steps. You can check this by actually listing all eight sequences of 1s and 2s that sum to 5 — it is a satisfying way to confirm the reasoning before trusting the formula for larger staircases.

Turning the recurrence into code

The recurrence translates almost word-for-word into a recursive Python function — a function that calls itself on smaller inputs:

def ways(n):
    if n <= 1:
        return 1
    return ways(n - 1) + ways(n - 2)

Call ways(5) and it correctly returns 8. The code looks almost too simple to be interesting — and for small staircases, it is genuinely fine. The trouble starts when the staircase gets taller, and it starts for a reason that is easy to miss unless you actually draw out what the computer is doing underneath.

Why the "obvious" version quietly becomes a disaster

When ways(5) runs, it does not just make one calculation — it triggers a cascade of function calls. ways(5) calls ways(4) and ways(3). ways(4) in turn calls ways(3) and ways(2). Notice that ways(3) just got called twice already, from two different places, and neither call knows about the other. Each one will redo the full calculation from scratch.

The diagram below draws out the complete call tree for ways(5). Every circle is one function call; the number inside is the staircase height that call is answering. Follow the branches and count carefully — this is exactly the kind of arithmetic a DP problem asks you to get right.

Count the circles: ways(5) appears once, ways(4) once, ways(3) twice, ways(2) three times, ways(1) five times, ways(0) three times. Add those up — 1 + 1 + 2 + 3 + 5 + 3 = 15 — and the plain recursive function makes fifteen separate function calls just to answer one question about a five-step staircase. But look at how many genuinely different questions are being asked: only six, the heights 0 through 5. Fifteen calls answering six distinct questions means nine of those calls are pure repeats — the exact same sub-question, with the exact same answer, computed again from nothing because the function has no memory of ever having seen it before.

Nine repeats out of fifteen calls does not sound catastrophic. It becomes catastrophic because the repetition compounds. Let C(n) be the total number of calls needed to compute ways(n) the plain recursive way. Since computing ways(n) means making one call for ways(n) itself, plus every call inside ways(n - 1), plus every call inside ways(n - 2):

C(n) = C(n - 1) + C(n - 2) + 1,   C(0) = C(1) = 1

Working this out: C(2) = 3, C(3) = 5, C(4) = 9, C(5) = 15 (matching the tree above), and it keeps climbing — C(10) = 177, C(15) = 1,973, C(20) = 21,891, and by C(30) it has passed 2,692,537 function calls to answer a question about a thirty-step staircase, a number small enough to state as a fact on a page but large enough that a real CBSE lab machine will take a noticeable pause to grind through it — and a staircase of 50 steps would take drastically longer still. The pattern roughly doubles every time n grows by about 1.4, which is the signature of exponential growth: brutally slow for large inputs even though each individual step of work is trivial. The staircase itself never got more complicated — climbing 30 steps 1-or-2-at-a-time is not conceptually harder than climbing 5 — but the naive code re-derives the same small facts millions of times over instead of remembering them.

The two properties that make a problem "dynamic-programmable"

Not every recursive problem has this issue, and knowing why the staircase problem does tells you exactly when dynamic programming applies. A problem is a good candidate for DP when it has two properties together:

• Overlapping subproblems. Solving the big problem requires solving the same smaller problem more than once, through different paths — exactly what the tree above shows for ways(3), ways(2), ways(1), and ways(0).
• A big answer that is built directly out of smaller answers. For optimization problems (find the best/cheapest/shortest something), this is usually called optimal substructure: an optimal solution to the whole problem can be assembled from optimal solutions to its pieces. For counting problems like the staircase, the analogous idea is that the total count is simply built by combining counts of smaller versions of the same problem — which is precisely what ways(n) = ways(n - 1) + ways(n - 2) does.

If a problem only has the second property but not the first — no subproblem is ever solved twice — then recursion is fine as it is, and adding memory to it would just waste memory for no speed gain. Merge sort is the classic example: it recursively sorts the left half of an array and the right half of an array, but those two halves are completely disjoint pieces of the original array. No sub-array is ever handed to a recursive call twice, so there is nothing to remember. That is the real dividing line between "just recursion" and "recursion that benefits from dynamic programming": overlap.

Fix #1 — memoization: remember answers the first time you compute them

Memoization keeps the original recursive structure but adds a notebook — a dictionary — that records the answer to every subproblem the first time it is solved. Before doing any work, a call checks the notebook; if the answer is already written down, it is returned immediately with no further recursion:

def ways_memo(n, memo=None):
    if memo is None:
        memo = {0: 1, 1: 1}
    if n in memo:
        return memo[n]
    memo[n] = ways_memo(n - 1, memo) + ways_memo(n - 2, memo)
    return memo[n]

Trace ways_memo(5): it needs ways_memo(4) and ways_memo(3). To get ways_memo(4), it needs ways_memo(3) and ways_memo(2); to get ways_memo(3), it needs ways_memo(2) and ways_memo(1), and ways_memo(1) is answered instantly from the notebook (1). Getting ways_memo(2) needs ways_memo(1) and ways_memo(0), both instant lookups, so memo[2] = 2 gets written down. Back up a level: memo[3] = memo[2] + memo[1] = 2 + 1 = 3 gets written down — the first and only time ways_memo(3) is ever actually computed. Back at ways_memo(4), it still needs ways_memo(3), but this time the notebook already has 3 sitting there, so it is a free lookup, not a recalculation. memo[4] = 3 + 2 = 5. Finally ways_memo(5) needs ways_memo(4) (notebook: 5) and ways_memo(3) (notebook: 3), giving 8 — correct, and each distinct height from 2 to 5 was genuinely computed exactly once. The wasteful branches in the tree above simply never get expanded a second time; they turn into single dictionary lookups instead.

Fix #2 — tabulation: build the answers from the ground up, no recursion at all

Tabulation (also called the "bottom-up" approach) throws away recursion entirely and instead fills an array from the smallest subproblem upward, in a simple loop:

def ways_tab(n):
    dp = [0] * (n + 1)
    dp[0] = 1
    if n >= 1:
        dp[1] = 1
    for i in range(2, n + 1):
        dp[i] = dp[i - 1] + dp[i - 2]
    return dp[n]

For n = 5, the array dp has 6 slots, indices 0 through 5. Set dp[0] = 1 and dp[1] = 1. Then the loop fills in the rest left to right: dp[2] = dp[1] + dp[0] = 1 + 1 = 2; dp[3] = dp[2] + dp[1] = 2 + 1 = 3; dp[4] = dp[3] + dp[2] = 3 + 2 = 5; dp[5] = dp[4] + dp[3] = 5 + 3 = 8. The function returns dp[5] = 8, matching every earlier method. No call ever branches into two more calls; the whole computation is one straight pass through the array, each slot filled exactly once using slots that are already sitting there. For this problem, tabulation needs only two numbers remembered at a time if you wanted to save memory further — you rarely need that in Grade 9 problems, but it hints at why tabulation is often preferred in performance-critical code: it avoids the memory used by a deep chain of waiting function calls.

Misconception: "memoization and tabulation are basically the same thing"

They compute identical answers, which is exactly why students often treat them as interchangeable — but they differ in real, checkable ways. Memoization works top-down: you still ask the big question first (ways_memo(5)), and it recursively asks smaller questions only as needed, so if some subproblems are never actually required to answer the original question, memoization never wastes time computing them. Tabulation works bottom-up: it fills in every single slot from 0 up to n, even ones that might not have been strictly necessary, but it does so with a plain loop instead of a chain of waiting function calls, which is usually faster in practice and cannot run into Python's recursion-depth limit the way a very tall memoized recursion chain eventually could.

The base case is where this distinction bites hardest, and a single missing line proves it. Compare ways_tab above with this deliberately broken variant:

def ways_buggy(n):
    dp = [0] * (n + 1)
    dp[1] = 1
    for i in range(2, n + 1):
        dp[i] = dp[i - 1] + dp[i - 2]
    return dp[n]

Spot the difference before reading on: dp[0] is never set to 1. Since Python initializes the list to all zeros, dp[0] silently stays 0. Trace ways_buggy(5): dp[1] = 1, so the array starts as [0, 1, 0, 0, 0, 0]. Then dp[2] = dp[1] + dp[0] = 1 + 0 = 1 — already wrong; it should be 2. The error does not crash anything and does not print a warning; it just quietly produces a smaller-than-correct number, and every later value inherits the mistake: dp[3] = dp[2] + dp[1] = 1 + 1 = 2, dp[4] = dp[3] + dp[2] = 2 + 1 = 3, dp[5] = dp[4] + dp[3] = 3 + 2 = 5. ways_buggy(5) returns 5 instead of the correct 8 — a plausible-looking number that happens to equal ways(4), which is exactly the kind of bug that survives a casual glance at the output. In dynamic programming, the base case is not decoration at the top of the function; it is the foundation every other value is built on, and getting it wrong corrupts the entire table without any error message to warn you.

A second problem: making change with the fewest tokens

The staircase problem was a counting problem. Dynamic programming is at least as useful for optimization problems — finding the best way to do something, not just counting the ways. Suppose your school's annual fest installed a token machine in the canteen that dispenses tokens in exactly three denominations: ₹1, ₹3, and ₹4 (a deliberately unusual set of values, chosen on purpose — the reason why comes shortly). If a student needs to pay a canteen bill of a given amount using the fewest tokens possible, how should the machine decide what to give?

Use the same "reason about the last move" idea as before. To make amount a with the fewest tokens, the very last token handed over was some value c from the allowed set (here, 1, 3, or 4), and before that last token, the remaining amount a - c must itself have been made with the fewest possible tokens — otherwise you could swap in a better solution for that leftover amount and do strictly better overall, which is exactly the optimal-substructure property named earlier. So:

dp[a] = 1 + min( dp[a - c] for every coin c <= a )

with dp[0] = 0 (zero tokens needed to pay nothing). As code, filling this in bottom-up, one amount at a time:

def min_coins(amount, coins):
    dp = [0] * (amount + 1)
    for a in range(1, amount + 1):
        best = None
        for c in coins:
            if c <= a:
                candidate = 1 + dp[a - c]
                if best is None or candidate < best:
                    best = candidate
        dp[a] = best
    return dp

Running min_coins(11, [1, 3, 4]) fills the table amount by amount. Work through a few by hand to see the pattern: for a = 3, the candidates are 1 + dp[2] (using a ₹1 token) and 1 + dp[0] (using the ₹3 token directly) — the second is cheaper, so dp[3] = 1. For a = 6, the candidates are 1 + dp[5], 1 + dp[3], and 1 + dp[2]; since dp[3] = 1, using a ₹3 token twice (1 + 1 = 2) wins. The full table for amounts 0 through 11:

A few of these are worth double-checking by hand because they are not obvious: ₹5 needs 2 tokens (₹4 + ₹1, since there is no single ₹5 token), ₹9 needs 3 tokens (₹3+₹3+₹3, or equally ₹4+₹4+₹1), and ₹11 needs 3 (₹4+₹4+₹3). If you continue the same table onward, ₹12 stays at 3 tokens (₹4+₹4+₹4), while ₹13 through ₹16 each need 4, and ₹17 needs 5 — the table keeps building the same way, each new amount reusing answers already sitting to its left.

Misconception: "just always hand over the biggest token you can"

Every student who has counted out change in rupees has an instinct that says: to minimize the number of coins, greedily grab the largest coin that fits, subtract it, and repeat. With India's real coins — ₹1, ₹2, ₹5, ₹10 — that instinct happens to always give the optimal answer, which is exactly why it feels like a law of arithmetic rather than a property of one particular set of denominations.

Apply the same greedy instinct to the fest's ₹1/₹3/₹4 tokens for an amount of ₹6, and it breaks. Greedy logic says: take the biggest token that fits first — ₹4 — leaving ₹2, then take ₹1, leaving ₹1, then take ₹1. That is three tokens (₹4 + ₹1 + ₹1). But the table above already proved dp[6] = 2, achieved with ₹3 + ₹3. Greedy overshoots by a whole token because grabbing the ₹4 first stranded a ₹2 remainder that this token set handles poorly, while a smarter choice avoided that trap entirely.

A second machine, stocked with ₹1, ₹4, and ₹5 tokens, makes the same mistake even more sharply for an amount of ₹8. Greedy takes ₹5 first, leaving ₹3, then three ₹1 tokens (no ₹3-valued token exists in this set) — four tokens in total. But ₹4 + ₹4 pays the same ₹8 with only two tokens, less than half of what greedy produced. Dynamic programming does not guess and hope; it genuinely checks every valid last token at every amount and keeps only the best, which is exactly why the min sits at the center of the recurrence. Greedy is a shortcut that happens to coincide with the true optimum only for specific, well-behaved denomination sets — real Indian coins among them — not a guarantee that holds for every possible set of values.

Summary

Dynamic programming is not a new kind of recursion — it is a discipline applied on top of ordinary recursive thinking, for problems where the same smaller question would otherwise get asked and answered from scratch many times over. The method has a fixed rhythm: reason about the last step to find a recurrence connecting an answer to smaller answers of the same kind; identify the base cases where the recurrence bottoms out; confirm that subproblems genuinely overlap (if they do not, plain recursion was never broken in the first place); and then either remember answers as you go with a dictionary (memoization, top-down) or build them up systematically in an array before you need them (tabulation, bottom-up). Both eliminate the repeated work that made the naive staircase function's runtime balloon from 15 calls at height 5 to over 2.6 million calls at height 30, while producing exactly the same numbers a correct plain-recursive version would — just without paying for the same answer twice. The two worked problems here, counting staircase paths and minimizing tokens for change, cover the two big families of DP problems you will meet again and again in Grade 9 and 10 computer science and in early competitive programming: counting how many ways something can happen, and optimizing the best way to do something — and in both families, the base case is not a formality to skim past, but the one line that everything else in the table is silently trusting.

Test Yourself

1. Using the "reason about the last move" technique, derive the recurrence for a staircase where you may climb 1, 2, or 3 steps at a time. State the recurrence and all necessary base cases.
2. Trace ways_tab(6) by hand, writing out the full dp array from index 0 to 6. What is ways(6)?
3. State the two properties a problem needs before dynamic programming helps. Explain, in terms of one of those two properties, why memoizing merge sort's recursive calls would not make it any faster.
4. In your own words, explain why calling the plain ways(n) function for a 30-step staircase takes noticeably longer to run than for a 5-step staircase — without using the word "recursion" or "recursive" anywhere in your answer.
5. Trace ways_buggy(4) by hand and state what it returns. Compare this to the correct value of ways(4), and explain in one sentence exactly which line causes the mismatch.
6. Using coins {1, 3, 4} and the recurrence dp[a] = 1 + min(dp[a - c]) over valid coins c, compute by hand the fewest tokens needed to make ₹9. Show which coin(s) achieve it.
7. Using coins {1, 4, 5}, show that always grabbing the largest valid coin fails for a target of ₹8, and state the true minimum number of coins along with a combination that achieves it.

Answers

1. ways3(n) = ways3(n - 1) + ways3(n - 2) + ways3(n - 3), with base cases ways3(0) = 1, ways3(1) = 1, and ways3(2) = 2 (the combinations 1+1 and 2). Check: ways3(3) = ways3(2) + ways3(1) + ways3(0) = 2 + 1 + 1 = 4, matching the four combinations 1+1+1, 1+2, 2+1, and 3.

2. dp = [1, 1, 2, 3, 5, 8, 13] for indices 0 through 6, computed as dp[6] = dp[5] + dp[4] = 8 + 5 = 13. So ways(6) = 13.

3. The two properties are overlapping subproblems and a big answer built directly from smaller answers (optimal substructure, for optimization problems). Merge sort's two halves of an array are disjoint pieces of the original — no sub-array is ever handed to the recursive call twice — so there is no overlap, and adding a memo dictionary would just spend memory checking for repeats that never happen.

4. The function keeps breaking each question about a staircase into two smaller questions about shorter staircases, and both of those smaller questions get answered completely from the beginning, even when the exact same short staircase has already been worked out somewhere else in the same calculation. For a 30-step staircase, a handful of small staircase heights end up being solved millions of times each instead of once, and it is this repeated, thrown-away work — not any single step being hard — that makes the plain version slow; the total effort roughly doubles every time a couple more steps get added to the staircase.

5. dp starts as [0, 1, 0, 0, 0] after setting dp[1] = 1. Then dp[2] = dp[1] + dp[0] = 1 + 0 = 1, dp[3] = dp[2] + dp[1] = 1 + 1 = 2, dp[4] = dp[3] + dp[2] = 2 + 1 = 3. So ways_buggy(4) returns 3, while the correct ways(4) = 5. The mismatch comes from the missing dp[0] = 1 line — dp[0] is silently left at its default value of 0 instead of the correct base case of 1, and every later value is built on top of that shortfall.

6. dp[9] = 1 + min(dp[8], dp[6], dp[5]) = 1 + min(2, 2, 2) = 3. Three tokens, achievable as ₹3 + ₹3 + ₹3, or equally ₹4 + ₹4 + ₹1.

7. Greedy on ₹8 with coins {1, 4, 5} takes ₹5 first (largest that fits), leaving ₹3, then three ₹1 tokens since no ₹3-valued coin exists — four tokens total. The true optimum uses ₹4 + ₹4, only two tokens, half of what greedy produced.

Think About It

Think about this: How would you explain dynamic programming: solving problems by remembering to a friend who has never seen a computer? What real-world analogy would you use? Imagine you had to build a system using these concepts — what would be your first step? Try this: before moving on, write down three things you learned and one question you still have.