Foundations — Tabulation (bottom-up DP) — iterative

This page assumes you have seen nothing. Before you can read the parent note Tabulation (bottom-up DP), you need to know what an array, an index, a subproblem, a recurrence, a base case, and the words max, substructure, and overlapping actually mean — as pictures, not jargon. We build each one, in order, each using the one before.

0. What is a "problem" and a "subproblem"?

The picture: imagine one big box labelled "climb 5". Inside it hide smaller identical boxes: "climb 4", "climb 3", … down to "climb 0". Each box is answerable on its own, and the big box's answer is made of the small boxes' answers.

Why the topic needs it: tabulation is literally "answer all the small boxes first, then combine." Without the idea that a problem contains smaller versions of itself, there is nothing to store and nothing to build up.

1. The array — a row of numbered boxes

The picture: think of an egg carton lying flat. Six cups in a line. Each cup can hold one number.

Why the topic needs it: the "table" in tabulation IS an array. It is the place where we write down every small answer so we never have to recompute it. The word table and the word array mean the same physical thing here.

2. The index $i$ — the box's house number

The picture: the egg-carton cups are numbered $0,1,2,3,4,5$ left to right — not starting at 1. The very first cup is house number $0$. This is a convention almost all code uses; get it into your bones now.

Why the topic needs it: every recurrence in the parent note is written using indices — $dp[i]$, $dp[i-1]$, $dp[i-2]$. If $i-1$ and $i-2$ confuse you, none of the recurrences will parse.

3. Neighbours: $dp[i-1]$ and $dp[i-2]$

Now that $i$ is a house number, the notation $dp[i-1]$ is just the box one step to the left, and $dp[i-2]$ is two steps to the left.

The picture: stand at cup $4$. Reach left to cup $3$ and cup $2$. Both already contain numbers, so you can add them and drop the result into cup $4$. You never reach right (to unfilled cups).

4. Base case — the boxes you fill by hand

The picture: you cannot reach "two steps left" from cup $1$ — that would be cup $-1$, which does not exist. So cups $0$ and $1$ must be placed by hand before the loop starts. They are the ground you stand on.

Why the topic needs it: the recurrence $dp[i]=dp[i-1]+dp[i-2]$ is undefined at the very start (it would read off the edge of the array). Base cases plug that hole. Forget them and the whole table stays zero or the program crashes reading $dp[-1]$.

5. Recurrence — the rule linking a box to its neighbours

Read it in English: "the answer at position $i$ equals the answer at $i-1$ plus the answer at $i-2$." The equals sign here means is computed as.

Why the topic needs it: the recurrence is the engine of the loop. Base cases give you the first two rungs; the recurrence manufactures every rung after that. Deeper math on why such relations are valid lives in Recurrence Relations.

6. The symbols $+$ vs $\max$ — and why the topic switches between them

Two different DP problems in the parent note use two different combining operations. You must know when each is correct.

• Use $+$ (addition) when you are counting things. In Climbing Stairs, the last move was either a 1-step or a 2-step. These two groups of paths never overlap, so the total count is group A plus group B. Counting disjoint possibilities ⇒ add.
• Use $\max$ when you are optimising (want the best). In 0/1 Knapsack you either take an item or skip it, and you want whichever gives more value. You are not counting — you are choosing the winner ⇒ max.

7. The 2D table — $dp[i][c]$, boxes with two house numbers

Some problems need two parameters at once. Then the table becomes a grid and each box has two indices: a row $i$ and a column $c$.

The picture: a chessboard of cups. To fill a cup, you now look at cups in the row above ($i-1$) and possibly a few columns to the left ($c-w$). As long as the whole previous row is finished, the current row can be filled in any order.

Why the topic needs it: 0-1 Knapsack and Longest Common Subsequence each track two things simultaneously (which items / which characters, and remaining capacity / position), so a 1D row is not enough.

8. Optimal substructure & overlapping subproblems — the two admission tickets

These are the two properties a problem MUST have before tabulation is even allowed.

The picture: a family tree of calls where the same node (e.g. "climb 2") appears in many branches. Overlapping = the tree has repeated nodes. Substructure = each parent node's value is a clean combination of its children's values.

Why the topic needs it: these two together define Dynamic Programming (Dynamic Programming). Tabulation and its cousin Memoization (top-down DP) are just two directions of exploiting them — bottom-up vs top-down.

Prerequisite map

Each arrow reads "is needed to understand". Follow any path top to bottom and you arrive, fully equipped, at Tabulation.

Equipment checklist

Cover the right side and test yourself. If any answer is fuzzy, re-read that section above before opening the parent note.

Connections

• Tabulation (bottom-up DP) — iterative — the parent topic these foundations unlock
• Dynamic Programming — the paradigm defined by the two admission tickets
• Optimal Substructure and Overlapping Subproblems — the two properties, in depth
• Recurrence Relations — the math behind step 5
• Memoization (top-down DP) — the top-down twin of tabulation
• 0-1 Knapsack, Longest Common Subsequence, Coin Change — where 2D tables appear
• Space Optimization in DP — shrinking the table once you understand it