Bottom-Up Tabulation

Foundations

Dynamic programming solves a problem from the answers to smaller versions of itself, each computed once and stored. In the Recursion course, memoization cached those answers as calls returned. Tabulation fills them in directly: an array dp where dp[i] holds the answer for a subproblem of size i, computed from earlier slots in a fixed order, smallest first.

Every table needs three things. A definition says what dp[i] means. A recurrence computes dp[i] from slots that are already filled, such as dp[i - 1] and dp[i - 2]. Base cases fill the first slots, which have no earlier slots to read. Fill from left to right, and every slot a cell reads is ready, so each one is computed exactly once.

In how many ways can nums = [7, 1, 5, 3, 6] be cut into consecutive pieces of length 1 or 2? Let ways[i] count the cuttings of its first i elements, so ways has n + 1 slots, 0 to 5. The last piece is one element or two, so ways[i] = ways[i - 1] + ways[i - 2], with ways[0] = ways[1] = 1. Filling left to right gives 1, 1, 2, 3, 5, 8: 8 ways.

• Memoized Recursion (Top-Down)

  That lesson cached each answer of a recursive count by its argument. A table stores the same answers, filled from the smallest up.

  Open lesson

Case Scenario

Climbing Stairs is that count with steps for elements: climbing n steps one or two at a time is cutting n elements into pieces of length 1 or 2. So ways[i] = ways[i - 1] + ways[i - 2], where ways[i] counts the ways to reach step i, starting from ways[0] = ways[1] = 1. For n = 5, the answer is 8.

The direct approach recurses: climbStairs(n) calls climbStairs(n - 1) and climbStairs(n - 2). Both branches solve the same smaller staircases again, so climbStairs(3) alone is computed twice for n = 5, and the number of calls grows about as fast as the answer, roughly 1.6ⁿ: millions of calls by n = 30.