Tabulation and 1D DP

Why it matters

The last lesson removed repeated work with a cache, but it still used recursion. Recursion has a cost: every waiting call takes a frame on the call stack, and very deep recursion can crash the program. The method in this lesson, tabulation, removes the recursion entirely. It is the form most interviewers expect to see, and it is the form most production DP code uses. It also tends to use less memory, and that is often the deciding factor when an input is large.

The skill you learn here is the most useful one in the whole module. You will write a sentence that defines what each table entry means, write a rule that computes an entry from earlier ones, and choose a loop order that makes sure those earlier entries exist when they are needed. Every problem later in the module follows that pattern, so take your time with it.

The idea

Think about building a staircase of bricks from the ground up. You cannot place the fifth course of bricks until the fourth course is in place, and the fourth course needs the third, and so on. You work from the bottom, and each new course rests on courses you have already finished.

Tabulation does the same thing with numbers. It is also called bottom-up DP, because you start at the smallest problems and build up to the big one. You create a table, fill in the entries that need no earlier entries, then fill in the next ones, and keep going until the answer cell is ready. No function calls itself, so no call stack grows.

Contrast this with the last lesson. Top-down (memoization) starts with the big question, asks itself smaller questions, and fills the table on the way back. Bottom-up (tabulation) starts with the small questions and fills the table in order. Both reach the same answer, and both do the same work for a fully solved table. The difference is how the order of work is chosen. Top-down chooses it by recursion. Bottom-up chooses it by a loop that you design.

Here is the recipe. You will follow it for every problem in this lesson.

1. Define what dp[i] means, in one plain sentence. Write the sentence as a comment before you write any code.
2. Set the base cases: the entries whose values you know without any recurrence.
3. Write the recurrence: the rule that computes dp[i] from entries with smaller indexes.
4. Choose the loop order so that every entry the rule needs has already been filled.
5. Read the answer from the right cell, and check it with a small input you can work out by hand.

Step 1 is the one that beginners skip, and it causes most wrong DP solutions. If you cannot write what dp[i] means, you cannot know whether your rule is right. Write the sentence first, every time.

The word 1D in the title means the table has one dimension, a single row of cells indexed by one number. Many problems need only that. The next lesson adds a second dimension for grids and pairs of strings.

Worked example: climbing stairs

You climb a staircase with n steps. Each move takes 1 step or 2 steps at a time. How many different sequences of moves take you from the ground to the top? The order matters: 1 then 2 is different from 2 then 1.

Step 1 of the recipe comes first. Let dp[i] mean "the number of ways to reach step i". Step 0 is the ground, so dp[0] is the number of ways to be on the ground, which is one (do nothing). Now step 2 of the recipe: the base cases are dp[0] = 1 and dp[1] = 1. From the ground you can reach step 1 in exactly one way, one move of 1 step.

Step 3 is the recurrence. Think about the last move that reached step i. That move was either a 1-step move from step i - 1, or a 2-step move from step i - 2. These two kinds of last move never overlap, so you add their counts:

dp[i] = dp[i - 1] + dp[i - 2]

Step 4 is the loop order. The rule for dp[i] reads dp[i - 1] and dp[i - 2], so those two must be filled first. A loop that goes from i = 2 up to n always fills the smaller indexes before it reads them. Step 5 is the answer, dp[n].

Here is the complete table for n = 5.

Table of ways to reach steps 0 to 5 for the stairs problem, values 1 1 2 3 5 8 with 8 highlighted

Each cell is one number, and each new cell is the sum of the two cells to its left. The sequence 1, 1, 2, 3, 5, 8 is the Fibonacci sequence again, which tells you the stairs problem and the Fibonacci function are the same problem in disguise. You have already met the recurrence, but now it is a loop, not a recursion.

The Viz below runs the same kind of table, one cell at a time. Step through it, and watch each cell appear only after the two cells it depends on are filled.

Now the code. This program reads n and prints the number of ways. It uses a vector for the table, sets the base cases, runs the loop, and returns the answer cell.

Type 10 in the Input box and press Run.

Output:

ways to climb 10 = 89

Look at the first line of climb. The table size is max(n, 1) + 1, not n + 1. When n is 0, the plain size n + 1 would be 1, and the next line writes dp[1], which is past the end of the vector. Taking the larger of n and 1 guarantees two cells, so the base cases always fit. This is a good habit: when base cases use index 1, make sure the table has index 1, whatever the input is.

The loop starts at i = 2, because the base cases already fill indexes 0 and 1. Each pass reads two cells to its left and writes one cell to the right. The loop does n - 1 passes, so the time is O(n). The table holds n + 1 numbers, so the space is O(n).

Worked example: house robber

Now a problem where the recurrence is less obvious. A street has houses in a row, and each house holds some cash. A thief may rob any set of houses, except that two neighbouring houses cannot both be robbed, because their alarms are linked. Find the largest total the thief can take.

Take the houses 2 7 9 3 1. A greedy idea says "rob the biggest house first", which takes 9. Then the thief cannot rob houses 2 and 4, so the best next choice is house 1 for 2, giving 11 in total. But robbing houses 1, 3 and 5 gives 2 + 9 + 1 = 12, which is better. Greedy fails, so we need DP.

Step 1: let dp[i] be the largest total from the first i houses. Here i counts houses, so dp[0] covers no houses and dp[5] covers all five. Step 2: the base cases are dp[0] = 0 (no houses, no cash) and dp[1] = houses[0] (one house, rob it).

Step 3, the recurrence. Look at the last house, which is house i in one-based counting. There are two choices. Skip it, and the best total is dp[i - 1], the best over the first i - 1 houses. Or rob it, and then house i - 1 must be skipped, so the best total is dp[i - 2] + houses[i - 1]. Take the larger of the two:

dp[i] = max(dp[i - 1], dp[i - 2] + houses[i - 1])

Notice the index shift. The array houses is zero-based, so the house that dp[i] adds is houses[i - 1]. Mixing these two indexes is the most common off-by-one error in this kind of problem, so write the shift in a comment.

Step 4: the loop goes up from i = 2 to n, so dp[i - 1] and dp[i - 2] are always filled. Step 5: the answer is dp[n]. Here is the table for 2 7 9 3 1.

Read the last cell. dp[5] = max(dp[4], dp[3] + houses[4]) = max(11, 11 + 1) = 12. The best choice for the last house is to rob it, and that is only allowed because house 4 was skipped in the best solution for the first four houses. The recurrence handles that automatically.

Trace the middle cells too. dp[2] = max(dp[1], dp[0] + houses[1]) = max(2, 0 + 7) = 7, so robbing house 2 beats keeping house 1. dp[3] = max(dp[2], dp[1] + houses[2]) = max(7, 2 + 9) = 11. Here robbing house 3 beats keeping the old best of 7.

The Viz below lets you step through the table cell by cell. It is the same kind of table, so the same pattern of reading two earlier cells applies. Watch which cells each new value looks at.

Keeping only two numbers

Look at the table again. Each cell depends only on the two cells just before it. Once dp[i] is computed, dp[i - 2] is never read again, so there is no reason to keep it. A table that stores only what is still needed is the first form of space optimisation, and it is one of the most common follow-up questions in interviews.

Instead of a table, keep two running numbers. take is the best total if the latest house is robbed, and skip is the best total if it is not. Each new house updates both. Here is the complete program. It reads the houses from the Input box.

Type 5 in the Input box, press Enter, then type 2 7 9 3 1 and press Run.

Output:

best total = 12

The order of the two assignments matters. newTake is computed first, because it needs the old skip. Then skip is updated, because it needs the old take. Only then is take set to newTake. If you swapped the order and updated take first, the new skip would read a value that was already overwritten. That is the bug listed in the mistakes section below.

The loop reads each house once and keeps two numbers, so the time is O(n) and the extra space is O(1). The function does not need a vector for its table at all. The houses vector is the input, not the table.

Printing a whole table

Sometimes you want to see every cell, not just the answer. Printing the table is the fastest way to check a DP solution, and it is the tool you will use most when something is wrong. The next program is the stairs program with every cell printed. It takes n from the Input box.

Type 6 in the Input box and press Run.

Output:

dp[0] = 1
dp[1] = 1
dp[2] = 2
dp[3] = 3
dp[4] = 5
dp[5] = 8
dp[6] = 13

Use this pattern during debugging. If the printed table does not match the table you worked out by hand, the bug is in the recurrence or the loop, and you can see the first wrong cell. A wrong final answer hides that information, but a printed table shows where the numbers first go wrong.

Maximum subarray: a 1D DP with a twist

The next problem is one of the most common interview questions. You are given a list of numbers, some positive and some negative. Find the largest possible sum of a contiguous run of numbers. Contiguous means the numbers sit next to each other in the list with no gaps. A run may be a single number.

Take -2 1 -3 4 -1 2 1 -5 4. The best run is 4 -1 2 1, which sums to 6. Notice that the run includes a negative number, -1. A run can include negative numbers when they connect two large positive numbers.

Here is the DP definition. Let best[i] be the largest sum of a contiguous run that ends exactly at position i. The word "exactly" is what makes the recurrence work. The run must end at i, so it either starts fresh at i or extends the best run that ends at i - 1:

best[i] = max(a[i], best[i - 1] + a[i])

If best[i - 1] is negative, adding it can only make things worse, so the run starts fresh at i. If it is positive, it is worth keeping. The answer is the largest value among all the best[i], because the best run may end anywhere in the list.

This version needs only the previous value, so it uses two variables: bestEndingHere for best[i] and bestSoFar for the running maximum. Here is the program. It reads the list from the Input box, and it handles an empty list.

Type 9 in the Input box, press Enter, then type -2 1 -3 4 -1 2 1 -5 4 and press Run.

Output:

best sum = 6

Follow the trace. Each row shows the list value, the new best[i], and the running answer.

Look at row 2. best[1] is 1, and adding -3 gives -2. That is worse than starting fresh at -3, but it is also worse than the earlier best of 1, so the answer stays at 1. Look at row 3. best[2] is -2, which is less than 4 by itself, so the run restarts at 4. That restart is the key decision the recurrence makes automatically. The method is called Kadane's algorithm, after Jay Kadane, who is usually credited with it, and it runs in O(n) time with O(1) extra space.

Why start with a[0] and not zero

Notice that the code sets both variables to a[0], not to zero. Think about a list with only negative numbers, such as -3 -1 -2. The best run must include at least one number, so the answer is -1, the single largest number. If the code started with zero, it would answer 0, which is a sum of an empty run and is not allowed by the problem. Starting from a[0] makes the answer a real sum from the list. This is one of the most common mistakes in the problem, and interviewers often check whether you think about it.

Recognising a 1D DP problem

Interviewers rarely say "use DP". You have to notice it yourself. Three signs point to a one-dimensional table.

The first sign is a question about a sequence. The input is a list, a row of houses, or a number n that counts steps, and the answer depends on the position in that list.

The second sign is a choice at each position that depends only on a few earlier positions. In the stairs problem, the choice is the size of the last move, and it depends on the two steps before. In house robber, the choice is rob or skip, and it depends on the previous house. When the dependency is short, the table is small.

The third sign is a question with a single number as the answer: a count, a minimum, a maximum, or a yes or no. Counting, minimising and maximising are the typical DP goals. If the question asks for the actual list of choices, you still use DP, but you also keep enough information to rebuild the choices.

Here is a quick test on a new problem. "A row of stones, each with a weight. Pick stones with no two adjacent, to maximise the total weight." The input is a list, the choice depends on the previous stone, and the answer is one number. That is house robber in different clothes, and the same recurrence works. Recognising the shape is most of the job.

Compare that with a problem that looks similar but is not. "Sort the houses by cash, then rob the richest ones." Sorting is not a choice that depends on earlier positions, and no table of prefix answers helps. Greedy or sorting ideas may apply, but DP is the wrong tool. Learning to say no is as useful as learning to say yes.

Working a small input by hand

Before you trust a program, work out a small case on paper and compare. Take n = 4 in the stairs problem. Write the table with a column for each step.

The entry at step 2 is 2, because you can reach it by two 1-steps or one 2-step. The entry at step 3 is 3, which is dp[2] + dp[1] = 2 + 1. The entry at step 4 is 5, which is dp[3] + dp[2] = 3 + 2. Now list the five ways to reach step 4 to check the table by a second method:

• 1, 1, 1, 1
• 1, 1, 2
• 1, 2, 1
• 2, 1, 1
• 2, 2

There are five, which matches dp[4]. The list also shows why the recurrence is right: every way ends with a 1-step from step 3 or a 2-step from step 2, and no way is counted twice.

Use this two-method check whenever you can. The table and the list are independent ways to reach the answer, so when they agree you have strong evidence. When they disagree, the difference shows you which step of the reasoning was wrong.

Top-down or bottom-up

You now know both styles. Here is a comparison to help you choose between them for a new problem.

Use top-down when the recurrence is easy to state but the set of needed states is unclear. Use bottom-up when you know the order of the states and the input is large. In interviews, bottom-up is usually the expected answer, because it has no recursion and its space can be reduced. Write the top-down version if it helps you think, then convert it.

What happens inside

It helps to know what the computer does with a table. A vector<long long> with n + 1 cells holds one contiguous block of memory. Each long long takes 8 bytes on a typical 64-bit system. A table of 1,001 entries therefore takes about 8,000 bytes, a little under 8 kilobytes. The loop walks through this block in order, so the processor reads memory in a predictable pattern, and that is one reason bottom-up code is fast in practice.

Compare that with the two-variable version. Its two variables are take and skip, plus the loop counter. They fit in CPU registers or the first few bytes of the stack frame. The space does not grow with n, which is the entire point of the optimisation.

The loop itself does one addition, one comparison and one assignment per cell. That is constant work per cell. The total work is the number of cells, which is O(n). If the recurrence did more work per cell, such as a loop over earlier cells, the total would grow faster. Keep an eye on the work per cell as well as the number of cells when you estimate the time.

Common mistakes

Not writing what dp[i] means. The rule for dp[i] looks right, but nobody can say what the number stands for. This is the root cause of most wrong DP solutions. Write the sentence first.

Reading a cell before it is filled. A loop that goes down when the recurrence reads smaller indexes reads zeros, because the cells have not been computed yet. The program still runs and prints a wrong number. Check the loop direction against the recurrence.

Missing base cases. Forgetting dp[0] or the empty-input case is a common source of errors. The stairs table needs dp[1] as well, which is why we size the table with max(n, 1).

Updating two running variables in the wrong order. In the house robber code, newTake must be computed before skip changes. If you write take = skip + money first and then skip = max(skip, take), the take you just wrote is used by skip, and the answer is wrong for some inputs. Write the old values into temporary variables when the update reads and writes the same names.

Using zero as the start value for a maximum. Kadane's algorithm must start from the first element. A zero start answers 0 for an all-negative list, and that is not a sum of a non-empty run.

Passing a negative size to a vector. If n is -1 and you write vector<long long> dp(n + 1), the size is 0, which is fine. But if n is -2, the size becomes -1, and C++ converts that to a huge unsigned number. The program stops with this message:

terminate called after throwing an instance of 'std::length_error'
  what():  cannot create std::vector larger than max_size()

Read the what() line. It says the size you asked for is impossible. The fix is to check that n is not negative before you size the table, because the problem's constraints should make that impossible and the check makes the failure visible.

Debugging walkthrough

Suppose you wrote the house robber program, and for the input 4 followed by 1 2 3 1 it prints 3 when the answer is 4. Here is how to find the cause without guessing.

First, work out the answer by hand. The best choice is houses 1 and 3, for 1 + 3 = 4. The program says 3, so something is wrong with the rule or the variables.

Second, print the state after each house. Add a line inside the loop that prints the house value, take and skip. Run it. Each line should match the table you would write by hand. If take after house 1 is 1, and after house 2 is 2, and after house 3 is 4, the program is correct so far.

Third, compare the lines with the hand trace. Suppose the printed take after house 3 is 3, not 4. Then the update for house 3 went wrong. Look at the code for that step. You will find that newTake = skip + money used a skip that was already updated, or that the max call uses the wrong pair of variables.

Fourth, fix the bug and run the same input again. Then try an input you have not checked, such as all equal values or a single house. A fix that works on one input can still fail on another.

The method is the same for every DP bug: check the definition, check the base cases, print the state, and compare with a hand trace.

Variations and edge cases

Test your DP code on these inputs before you trust it.

• An empty list of houses. The answer is 0, and the loop should not run at all.
• One house. The answer is the house's value, because there is nothing to skip.
• Two houses. The answer is the larger of the two, not their sum.
• Equal values in every house. The answer depends on whether n is even or odd, which is a good check on the parity of the choices.
• An all-negative list for Kadane's algorithm. The answer is the largest single element.
• A list where the best run is the whole list. The answer is the sum of everything, and the program must not stop early.

For the stairs problem, the variations are about the step sizes. If the staircase allows steps of 1, 2 or 3, the recurrence adds a third term, dp[i - 3], and the base cases become dp[0], dp[1] and dp[2]. If each step has a cost, the sum becomes a minimum, and you add the cost of the step you land on. Those two changes are good practice exercises, and you will see them in the practice list below.

Interview questions

These are the kinds of questions interviewers ask about one-dimensional DP. The short answers show the expected depth.

"How do you know the loop order is right?" Answer: the recurrence tells you which cells it reads. The loop must fill those cells first. For dp[i] that reads dp[i - 1], a loop that goes up in i works. Name the cells it reads and show that they are already filled.

"Can you reduce the memory?" Answer: yes, if each cell reads only a fixed number of earlier cells. Keep just those cells. The stairs and house robber problems each need two values, so the space is O(1).

"What is the complexity of Kadane's algorithm?" Answer: O(n) time, because each element is visited once and the work per element is constant. O(1) extra space, because only two running values are kept.

"Why does greedy fail on house robber?" Answer: taking the biggest house can block two good houses, and no local choice tells you when to give up a big house for two smaller ones. DP compares the whole set of options through the recurrence.

"How would you return the houses that were robbed?" Answer: keep the full table and walk back from dp[n]. At each house, if dp[i] equals dp[i - 1], that house was skipped. Otherwise it was robbed, and you jump back two positions. This takes O(n) extra space for the table.

Practice

1. Easy. Change the stairs program so the moves may be 1, 2 or 3 steps. Write the new recurrence and the base cases. Predict the answer for n = 4 before you run it.

2. Easy. Run the house robber logic on 1 2 3 1 by hand. Write the table of dp values. The answer should match the value you found in the debugging walkthrough.

3. Easy. Write one sentence that defines dp[i] for the stairs problem and one for the house robber problem.

4. Medium. Minimum cost climbing. Each step i has a cost, and you pay that cost when you stand on the step. You may start on step 0 or step 1 for free. From step i you may move to i + 1 or i + 2. The top is one step past the last step. For the costs 10 15 20, the answer is 15. Write the recurrence and the answer formula.

5. Medium. Count the binary strings of length n that have no two 1 digits next to each other. For n = 1 there are 2 strings, and for n = 3 there are 5. Find the recurrence and show that it is the same shape as the stairs problem.

6. Medium. Trace Kadane's algorithm on 5 -9 6 -2 3 and write the table of best[i] values. Predict the answer before you check it.

7. Medium. Explain why the Kadane program fails if it starts both variables at zero, using the list -3 -1 -2 as your example.

8. Medium. Change the house robber program so that it prints which houses were robbed, not only the total. You may use a full table for this.

9. Hard. Count the ways to tile a board that is 2 units high and n units long with dominoes that are 2 by 1. A domino may lie flat or stand up on a single column. For n = 4 the answer is 5. Find the recurrence.

10. Hard. Rewrite the minimum cost climbing solution so that it uses only two variables, not a table. Explain why two variables are enough.

What you now know

• Tabulation fills a table from the smallest case up with a loop, and it needs no recursion.
• The first step of every DP solution is a sentence that defines what each entry means.
• The base cases set the first entries, and the table must be large enough to hold them.
• A recurrence reads earlier cells, so the loop order must fill those cells first.
• When a cell reads only a few earlier cells, you can keep just those values and save memory.
• Kadane's algorithm is a 1D DP that finds the largest contiguous sum in O(n) time.
• Printing the table is the fastest way to find the first wrong cell.
• The next lesson moves to two dimensions, with grids and the knapsack problem.