Dynamic Programming — Tabulation

Introduction

In the previous post, we explored Top-Down Memoization. We wanted the answer for $F(50)$, so we boldly called fibMemo(50), which recursively asked for fibMemo(49), which asked for fibMemo(48), all the way down to $F(0)$.

This is highly intuitive, but it has two drawbacks:

1. Recursion Overhead: Every function call adds a frame to the Call Stack, which takes time and memory.
2. StackOverflow Risk: If you ask for fibMemo(100000), the Call Stack will exceed its limit and crash your program before it even hits the base cases.

Tabulation (Bottom-Up DP) solves this. Instead of starting at the target and asking “What do I need?”, we start with the base cases and build upwards iteratively using loops, filling in a “table” (an array) as we go.

Tabulating the Fibonacci Sequence

Let’s re-solve the Fibonacci problem using Tabulation.

We know the base cases:

• table[0] = 0
• table[1] = 1

Instead of recursing, we just use a for loop starting from i = 2 up to n. Every slot i looks back at i-1 and i-2.

Java Implementation

public class FibonacciTabulation {

    public static long fibTab(int n) {
        if (n <= 1) return n; // base cases

        // 1. Create the table
        long[] dp = new long[n + 1];

        // 2. Initialise the base cases in the table
        dp[0] = 0;
        dp[1] = 1;

        // 3. Fill the table iteratively (Bottom-Up)
        for (int i = 2; i <= n; i++) {
            dp[i] = dp[i - 1] + dp[i - 2];
        }

        // 4. Return the final answer at the end of the table
        return dp[n];
    }

    public static void main(String[] args) {
        System.out.println(fibTab(50)); // Output: 12586269025
    }
}

Top-Down vs Bottom-Up Comparison

The Ultimate Space Optimisation

Here is where Tabulation shines. Look at the for loop in the code above: dp[i] = dp[i - 1] + dp[i - 2];

When calculating dp[10], we only look at dp[9] and dp[8]. We don’t care about dp[7], dp[6], or dp[0] anymore.

So why are we storing them in a massive array? We can optimise our memory from $O(n)$ down to $O(1)$ by only keeping track of the last two variables.

public static long fibOptimised(int n) {
    if (n <= 1) return n;

    long prevTwo = 0; // Represents dp[i-2]
    long prevOne = 1; // Represents dp[i-1]
    long current = 0;

    for (int i = 2; i <= n; i++) {
        current = prevOne + prevTwo; // Calculate current
        
        // Shift variables forward for the next iteration
        prevTwo = prevOne;
        prevOne = current;
    }

    return current;
}

This is the holy grail of DP: $O(n)$ time and $O(1)$ space! You cannot do this with recursive memoization.

2D Tabulation: Minimum Path Sum

Let’s look at a 2D problem: You are at the top-left of an $M \times N$ grid, trying to reach the bottom-right. You can only move Right or Down. Each cell contains a cost. Find the path that minimises the total cost.

The State Transition: To reach cell (row, col), you must have come from either (row-1, col) (Above) or (row, col-1) (Left). Therefore: costToReachHere = currentCellCost + min(costFromAbove, costFromLeft).

Step-by-Step Tabulation

Given this 3x3 matrix:

1  3  1
1  5  1
4  2  1

1. Base Case: We start at [0][0]. The cost is just 1. 2. First Row: We can only reach the top row from the left.

• [0][1] = 1 + 3 = 4
• [0][2] = 4 + 1 = 5 3. First Column: We can only reach the left column from above.
• [1][0] = 1 + 1 = 2
• [2][0] = 2 + 4 = 6

Current DP Table:

 1   4   5
 2   ?   ?
 6   ?   ?

4. Fill the rest: For [1][1] (cost 5), we look at Above (4) and Left (2). Left is smaller.

• [1][1] = 5 + min(4, 2) = 7.

We continue this row by row, column by column. The final answer will be in the bottom-right corner.

Java Implementation

public class MinPathSum {

    public static int minPathSum(int[][] grid) {
        int rows = grid.length;
        int cols = grid[0].length;

        // Note: We can optimise space by overwriting the original grid
        // instead of creating a new 2D DP array!

        // Fill first row
        for (int c = 1; c < cols; c++) {
            grid[0][c] += grid[0][c - 1];
        }

        // Fill first col
        for (int r = 1; r < rows; r++) {
            grid[r][0] += grid[r - 1][0];
        }

        // Fill the rest
        for (int r = 1; r < rows; r++) {
            for (int c = 1; c < cols; c++) {
                grid[r][c] += Math.min(grid[r - 1][c], grid[r][c - 1]);
            }
        }

        // The answer is at the bottom-right
        return grid[rows - 1][cols - 1];
    }
}

Memoization vs Tabulation: Which to choose?

1. Start with Memoization Always try the Top-Down recursive approach first on a whiteboard. It is much easier to reason about the problem when you just ask “what variables do I need to pass into my recursive function?”.
2. Convert to Tabulation if needed Once you have the recursive relation (e.g. dp(i) = cost + min(dp(i-1), dp(j-1))), converting it to an iterative table is usually straightforward. Do this if you fear StackOverflows or if you spot a way to optimise the space complexity down to $O(1)$ by removing the arrays.

Practice Problems

1. Coin Change – LeetCode #322 — A classic unbounded knapsack problem. Build an array from 0 to amount and fill it bottom-up.
2. Unique Paths – LeetCode #62 — Same logic as the Minimum Path Sum problem above, but substituting min() with +.
3. Longest Common Subsequence – LeetCode #1143 — The ultimate 2D string tabulation challenge.

What’s Next?

Dynamic Programming is thorough. It looks at every possible valid option, caches them, and gives you the mathematically proven optimal answer.

But sometimes… we don’t need to look at every option. Sometimes, making the stubbornly selfish “best immediate choice” at every step magically leads to the global optimal solution. That is the philosophy behind our next topic: Greedy Algorithms.