The bottom-up approach: filling a table

There is a second way to apply dynamic programming, without any recursion: the bottom-up approach. Instead of starting from the big problem and working back down to the small cases (as with memoization), you start from the smallest cases and work your way up, filling a table dp, cell by cell.

Let's take a classic example: counting the number of ways to climb a staircase of n steps, knowing that each step forward advances by 1 or 2 stairs. Let dp[i] denote this number of ways for i stairs. To reach stair i, you necessarily come either from stair i-1 (by climbing 1 stair), or from stair i-2 (by climbing 2 stairs). So dp[i] = dp[i-1] + dp[i-2] — this is exactly the Fibonacci recurrence, but applied to a real, concrete problem.

We initialize dp[0]=1 (a single way to stay in place: do nothing) and dp[1]=1 (a single way to reach stair 1: one step of 1). Watch the table fill in step by step for n=6:

dp[0] = 1                          (base: 0 stairs, 1 way = do nothing)
dp[1] = 1                          (base: 1 stair, 1 way = step of 1)
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
dp[6] = dp[5] + dp[4] = 8 + 5 = 13

final table: [1, 1, 2, 3, 5, 8, 13]
                  0  1  2  3  4  5  6   (index = number of stairs)

Each cell depends only on the two previous cells already filled in: there is never any need to recompute anything, since progress is always made forward. This is the very spirit of bottom-up dynamic programming: build the solution from the bottom up, systematically reusing what has already been placed in the table.