Articles

The site’s easiest dynamic programming exercise starts with a staircase. You can climb one or two steps at a time. How many different ways can you use to reach the top of an $n$ -step staircase? The last step came from either step $n-1$ or step $n-2$ , so the number of ways to reach $n$ is the number of ways to reach $n-1$ plus the number of ways to reach $n-2$ :

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

That is a complete, correct program: two base cases and one recursive line. It is also a trap. The same two-line recursion that solves Climbing Stairs quickly for small inputs falls apart as $n$ grows. The fix is one of the most important ideas in algorithms. It is called dynamic programming. The site has taught the same idea since the Substitutions exercises. The useful short version is recursion with a cache.

The problem with naive recursion

Write the climbing-stairs recursion as a function and run it for $ways(10)$ , which is 89. The function computes $ways(9)$ and $ways(8)$ . Each of those computes its own two predecessors, down to the base cases. The recursion tree doubles at every level. The number of calls grows like $2^n$ , and most calls are the same call. $ways(8)$ is computed once as a child of $ways(10)$ , again as a child of $ways(9)$ , and again inside $ways(9)$ ’s other branch. The function starts from scratch each time, even for values it already produced.

The waste is easy to measure. The same recursion shape produces the Fibonacci numbers. Computing the 40th Fibonacci number with the naive two-line recursion performs roughly 331 million function calls. The answer, 102,334,155, fits in a 32-bit integer. The recursion makes hundreds of millions of calls to produce a number a spreadsheet can hold. The data-structures text gives this condition a name: overlapping subproblems - the same smaller problems appearing again and again inside different branches of the recursion. Its definition of dynamic programming names that condition and its remedy:

Dynamic programming is the process of optimizing recursive problems that have overlapping subproblems.

That is the whole definition. Dynamic programming is not a new kind of algorithm. Repair the recursive one in two steps: notice that it recomputes the same subproblems, then stop it from doing that.

Memoization: the cache

The fix has a name that looks like a typo but is not one. Memoization - the text is careful to point out that the word is correct - changes the recursion by one line: before computing a value, check whether it is already stored.

Memoization is a simple, but brilliant, technique for reducing recursive calls in cases of overlapping subproblems.

In practice, memoization usually uses an array or table keyed by the function’s input. The competitive-programming reference states the mechanism precisely: “The key idea in dynamic programming is memoization, which means that we store each function value in an array directly after calculating it. Then, when the value is needed again, it can be retrieved from the array without recursive calls.”

Apply that to the staircase. When the recursion computes $ways(8)$ for the first time, store the result under key 8. Every later request for $ways(8)$ - from $ways(9)$ or from $ways(10)$ ’s other branch - finds the stored value and returns it in constant time. It does not recompute the subtree. The recursion tree collapses. There is one value per distinct input instead of one subtree per call. The naive recursion’s 331 million calls for the 40th Fibonacci number become 41 - one for each distinct subproblem from 0 to 40, each computed once and reused thereafter. That is the difference between $2^n$ and $n$ . It is also the difference between never finishing and finishing instantly. The site’s What O(n) actually promises article supplies the vocabulary: growth determines the cost, and memoization changes that growth.

Why the cache is allowed: the site’s own core lesson

A cache is sound only when it cannot change the answer. If a function could return a different value for the same input depending on when it was called - on a counter it incremented, on global state it mutated, or on the time of day

then storing the first result and reusing it later would be wrong. It would misrepresent the function’s behavior. Every memoized dynamic program quietly depends on the function it memoizes being pure: same input, same output, no side effects.

That property has a name the site has drilled from the first exercises: referential transparency. A call is referentially transparent when you can replace it with its result without an observable change in behavior. That is the license memoization needs. The Substitutions and Functions exercises teach that an expression reduces to a value by replacing equals with equals. Memoization applies the same idea: since $ways(8)$ always is 34, storing 34 where the value was computed is not just an optimization; it is a substitution the program performs. The Reading Elixir as a JS developer article connects this to the site’s language of choice: a functional language makes the pattern natural because its model of computation - values flowing through pure functions - matches the assumption the cache needs.

This is why dynamic programming fits a functional-thinking site so well. The usual framing of DP as a “technique” hides the source of its payoff: the purity the site teaches from lesson one. Once you understand referential transparency, dynamic programming is not a new idea. The next step is obvious: “my function is pure, so I may cache it.” The name - which the data-structures text cheerfully warns not to overthink: “there’s nothing obviously dynamic about the techniques I’m about to demonstrate” - matters less than that reasoning.

From recursion to table

Memoization keeps the recursion and adds a table. You can compute the same numbers the other way: fill the table from the bottom up, from the base cases to the answer, without recursion. Compute $ways(1)$ , then $ways(2)$ , then $ways(3)$ . Each new value is the sum of the two values before it, already in the table. The competitive-programming reference describes the same idea: the value comes from the array instead of being recomputed. Fill the table on the way down (memoization) or on the way up (tabulation). That is a style choice, not a different algorithm. The recursion tree and the filled table show the same structure from opposite directions.

The bottom-up version is short enough to read at a glance. It uses the same recurrence, carrying two values forward instead of re-descending:

defmodule Ways do
  def climb(n) when n <= 2, do: n

  def climb(n) do
    Enum.reduce(3..n, {1, 2}, fn _, {a, b} -> {b, a + b} end)
    |> elem(1)
  end
end

Ways.climb(10) returns 89, matching the recursion. It avoids the 331-million-call overhead, and it needs no memo table because the loop carries only the two values it will use next. The functional shape - a pure function reducing over a range and producing a new pair each step - is the same idea the Recursion article teaches. Here, the cache is structural rather than explicit.

Bottom-up vs top-down, without mutating a cache

The pair {a, b} is enough for climbing stairs because each answer uses only the two predecessors. The general case - coin change, house robber, a count of subsets - needs the whole table. Two directions fill that table. Both stay immutable.

Top-down is memoization: keep the recursive shape, and pass an accumulating Map down the call. Return {value, cache}, not the value alone. A hit is {cached, cache}. A miss recurses with the cache the previous call returned - {a, cache} = memo(n - 1, cache), then {b, cache} = memo(n - 2, cache) - so each step sees the fills already stored, then returns {value, Map.put(cache, n, value)}. Drop that map and later calls recompute. Thread it and ways(8) is stored once. The old map is unchanged: that is the substitution already taught.

defmodule Ways.Memo do
  def climb(n), do: memo(n, %{}) |> elem(0)

  defp memo(n, cache) when n <= 2, do: {n, cache}

  defp memo(n, cache) do
    case Map.fetch(cache, n) do
      {:ok, cached} ->
        {cached, cache}

      :error ->
        {a, cache} = memo(n - 1, cache)
        {b, cache} = memo(n - 2, cache)
        value = a + b
        {value, Map.put(cache, n, value)}
    end
  end
end

Ways.Memo.climb(10) returns 89. The {value, cache} pair is the whole trick: elem(0) is the answer, and every recursive step received the map that previous steps filled.

Bottom-up is tabulation: start from the base cases and Map.put each next key until you reach n. Same map, no recursion, still no in-place write. The Enum.reduce below threads the table the same way: each step’s Map.put is the next step’s table.

defmodule Ways do
  def climb(n) when n <= 2, do: n

  def climb(n) do
    3..n
    |> Enum.reduce(%{1 => 1, 2 => 2}, fn k, table ->
      Map.put(table, k, table[k - 1] + table[k - 2])
    end)
    |> Map.fetch!(n)
  end
end

The JavaScript analogue is object spread, not an assignment into a cache object. A new object each step:

function climb(n) {
  if (n <= 2) return n;
  const keys = Array.from({ length: n - 2 }, (_, i) => i + 3);
  const table = keys.reduce(
    (acc, k) => ({ ...acc, [k]: acc[k - 1] + acc[k - 2] }),
    { 1: 1, 2: 2 }
  );
  return table[n];
}

Ways.climb(10) and climb(10) both return 89. The taught path never mutates a cache object. Assigning into one in place is the same idea with a side effect, and it is the default in a lot of textbook JavaScript. This site’s languages of choice make the immutable form the default, so that is the form to think in. When a problem needs the full table, carry a Map (or a list you rebuild) - do not poke a cache.

Coin change: the greedy trap

The staircase is a warm-up. The site’s Coin Change exercise is where dynamic programming earns its keep: given coins of distinct denominations and a total amount, return the fewest coins needed to make that amount, or -1 if it cannot be made, with unlimited coins of each denomination.

The trap is a simple algorithm that looks right: the greedy one - always take the largest coin that fits, then repeat. The competitive-programming reference opens its dynamic programming chapter with exactly this warning: “There is a simple greedy algorithm for the problem, but as we will see, it does not always produce an optimal solution. However, using dynamic programming, we can create an efficient algorithm that always finds an optimal solution.”

The counterexample is tiny. With coins 1, 3, and 4, make 6. The greedy algorithm takes a 4, then a 1, then a 1: three coins. But 3 plus 3 makes 6 with two coins. Greedy sees the largest immediate step and misses the future. It cannot know that two 3s beat a 4 plus two 1s because the optimal answer depends on the combination of choices, not one choice. Dynamic programming checks the whole space. The fewest coins for amount 6 is one coin plus the fewest coins for amount 2 (using a 4), amount 3 (using a 3), or amount 5 (using a 1). The recursion chooses the best option, memoized. The greedy failure mode is a whole topic of its own. The recognition skill - “this is an optimization over combinations, greedy won’t do” - is the class recognition move the site’s Algorithms past the interview article names as the heart of the handshake.

The wider shapes

Once you can see the pattern - recursion, overlapping subproblems, memoize or tabulate - the site’s other dynamic programming exercises use the same pattern in different settings:

House Robber: a choose/not-choose decision at each house, where the best answer at position $i$ depends on the best answer at $i-1$ and $i-2$ . Same staircase, different story.
Maximum Subarray: the recurrence is “the best sum ending here“ - either extend the previous best or start fresh
- and the answer is the best of the endings. The textbook’s “optimal solutions” phrasing is doing real work: DP answers best questions as well as count questions.
Subset Sum Count: counting how many subsets sum to a target - the “count the number of solutions” half of the definition, and the same combinatorial space the P vs NP article warns about. The count does not explode because the table stores counts per target, not per subset.

The competitive-programming reference’s definition covers both halves in one sentence: “Dynamic programming is an algorithm design technique that can be used to find optimal solutions to problems and to count the number of solutions.” Find the best, or count them all - both are recursion with a cache.

Where to go next

Climbing Stairs - the warm-up: the recurrence in the article, solved for real.
Coin Change - the greedy trap and the DP escape, in the grader.
House Robber and Maximum Subarray - the decision and best-ending shapes.
Subset Sum Count - the counting half, and the combinatorial explosion DP tames.
Recursion and Induction - the machinery dynamic programming is built from: recursion for structure, induction for the proof that the recursion covers every case.
Substitutions and Functions - the purity that makes the cache sound.
What O(n) actually promises - the $2^n$ to $n$ shape change that memoization buys.

Dynamic programming is recursion with a cache. The cache is allowed because of the property this site teaches first: pure functions give the same output for the same input, so storing that output is never a lie. The naive recursion is not wrong. It computes the right answer 331 million times over. Dynamic programming does not replace it. It gives the recursion memory of what it already knew and tells it to stop repeating itself.

Dynamic programming: recursion with a cache