Top-down and bottom-up

Lesson · 11 min read · Dynamic programming · Order of computation

Compute the same recurrence either by memoised recursion or by filling a table in dependency order. How to choose, and how to save memory.

Two ways to evaluate one recurrence

Top-down (memoisation) keeps the recursive function and adds a cache: before computing a state, look it up; after computing it, store it. The recursion visits states in whatever order the calls happen to need them.

from functools import lru_cache

def grid_paths(rows, cols):
    @lru_cache(maxsize=None)
    def paths(r, c):
        if r == 0 or c == 0:
            return 1
        return paths(r - 1, c) + paths(r, c - 1)
    return paths(rows - 1, cols - 1)

long long grid_paths(int rows, int cols) {
    std::vector<std::vector<long long>> memo(rows, std::vector<long long>(cols, -1));
    std::function<long long(int, int)> paths = [&](int r, int c) -> long long {
        if (r == 0 || c == 0) return 1;
        if (memo[r][c] != -1) return memo[r][c];
        return memo[r][c] = paths(r - 1, c) + paths(r, c - 1);
    };
    return paths(rows - 1, cols - 1);
}

static long gridPaths(int rows, int cols) {
    return paths(rows - 1, cols - 1, new long[rows][cols]);
}

static long paths(int r, int c, long[][] memo) {
    if (r == 0 || c == 0) return 1;
    if (memo[r][c] != 0) return memo[r][c];
    return memo[r][c] = paths(r - 1, c, memo) + paths(r, c - 1, memo);
}

function gridPaths(rows, cols) {
    const memo = new Map();
    const paths = (r, c) => {
        if (r === 0 || c === 0) return 1;
        const key = r * cols + c;
        if (!memo.has(key)) memo.set(key, paths(r - 1, c) + paths(r, c - 1));
        return memo.get(key);
    };
    return paths(rows - 1, cols - 1);
}

fn grid_paths(rows: usize, cols: usize) -> u64 {
    fn paths(r: usize, c: usize, memo: &mut Vec<Vec<Option<u64>>>) -> u64 {
        if r == 0 || c == 0 { return 1; }
        if let Some(v) = memo[r][c] { return v; }
        let v = paths(r - 1, c, memo) + paths(r, c - 1, memo);
        memo[r][c] = Some(v);
        v
    }
    let mut memo = vec![vec![None; cols]; rows];
    paths(rows - 1, cols - 1, &mut memo)
}

gridPaths :: Int -> Int -> Integer
gridPaths rows cols = table ! (rows - 1, cols - 1)
  where
    -- a lazy array is the memo table: each cell is computed once, the first time it is read
    table = listArray ((0, 0), (rows - 1, cols - 1)) [paths r c | r <- [0 .. rows - 1], c <- [0 .. cols - 1]]
    paths r c
      | r == 0 || c == 0 = 1
      | otherwise = table ! (r - 1, c) + table ! (r, c - 1)

Bottom-up (tabulation) drops the recursion and fills a table in an order where every state's dependencies are already filled. For paths(r, c) that order is row by row, left to right.

def grid_paths(rows, cols):
    t = [[1] * cols for _ in range(rows)]      # row 0 and column 0 are base cases
    for r in range(1, rows):
        for c in range(1, cols):
            t[r][c] = t[r - 1][c] + t[r][c - 1]
    return t[rows - 1][cols - 1]

long long grid_paths(int rows, int cols) {
    std::vector<std::vector<long long>> t(rows, std::vector<long long>(cols, 1));   // row 0 and column 0 are base cases
    for (int r = 1; r < rows; ++r)
        for (int c = 1; c < cols; ++c)
            t[r][c] = t[r - 1][c] + t[r][c - 1];
    return t[rows - 1][cols - 1];
}

static long gridPaths(int rows, int cols) {
    long[][] t = new long[rows][cols];
    for (long[] row : t) Arrays.fill(row, 1);      // row 0 and column 0 are base cases
    for (int r = 1; r < rows; r++)
        for (int c = 1; c < cols; c++)
            t[r][c] = t[r - 1][c] + t[r][c - 1];
    return t[rows - 1][cols - 1];
}

function gridPaths(rows, cols) {
    const t = Array.from({ length: rows }, () => new Array(cols).fill(1));   // row 0 and column 0 are base cases
    for (let r = 1; r < rows; r++)
        for (let c = 1; c < cols; c++)
            t[r][c] = t[r - 1][c] + t[r][c - 1];
    return t[rows - 1][cols - 1];
}

fn grid_paths(rows: usize, cols: usize) -> u64 {
    let mut t = vec![vec![1u64; cols]; rows];      // row 0 and column 0 are base cases
    for r in 1..rows {
        for c in 1..cols {
            t[r][c] = t[r - 1][c] + t[r][c - 1];
        }
    }
    t[rows - 1][cols - 1]
}

gridPaths :: Int -> Int -> Integer
gridPaths rows cols = last (iterate (scanl1 (+)) (replicate cols 1) !! (rows - 1))
  -- row 0 is all ones; each later row is the running sum of the row above,
  -- which is exactly t[r][c] = t[r - 1][c] + t[r][c - 1] with t[r][0] = 1

Bottom-up for a 4 × 5 grid: every cell reads two cells that are already filled.

Step 1 / 13

Base cases filled first.
Step 2 / 13

(1, 1) = 1 from above + 1 from the left = 2.
Step 3 / 13

(1, 2) = 1 from above + 2 from the left = 3.
Step 4 / 13

(1, 3) = 1 from above + 3 from the left = 4.
Step 5 / 13

(1, 4) = 1 from above + 4 from the left = 5.
Step 6 / 13

(2, 1) = 2 from above + 1 from the left = 3.
Step 7 / 13

(2, 2) = 3 from above + 3 from the left = 6.
Step 8 / 13

(2, 3) = 4 from above + 6 from the left = 10.
Step 9 / 13

(2, 4) = 5 from above + 10 from the left = 15.
Step 10 / 13

(3, 1) = 3 from above + 1 from the left = 4.
Step 11 / 13

(3, 2) = 6 from above + 4 from the left = 10.
Step 12 / 13

(3, 3) = 10 from above + 10 from the left = 20.
Step 13 / 13

(3, 4) = 15 from above + 20 from the left = 35. The answer, 35, is in the bottom-right cell.

Choosing the order

A valid order is a topological order of the subproblem graph: any order in which each state comes after the states it reads. In practice it is one of a few shapes:

1-D, reading smaller indices: left to right.
Prefixes of two sequences: row by row, each row left to right.
Intervals [i, j]: by increasing length, because an interval reads shorter ones.
Knapsack (item, capacity): item by item; within an item, the capacity order depends on whether the item may be reused (see the knapsack modules).

Which to use

A good habit in interviews: write top-down first to get the recurrence right, then convert to bottom-up if the interviewer asks for speed, iteration or less memory.

	Top-down	Bottom-up
Writing it	closest to the recursion; fastest to get right	needs the order worked out
States computed	only those actually reachable	all of them
Recursion depth	can overflow the stack (Python: about 1,000)	none
Speed	call and cache overhead	tight loops
Saving memory	hard	easy: keep only the rows still needed

Timestates × work per state

Spacestates, or less with rolling rows

In the grid each row reads only the row above, so one row of length cols is enough: O(cols) memory instead of O(rows · cols). Fibonacci-style recurrences need only the last two values.