🎓 A1Learner
🔍
0 of 47 lessons completed

Tabulation: Building Up a Table

Tabulation is the technique of building a table of answers from the smallest input upward. Each row of the table is filled from rows already filled.

The recognition signal

A problem fits a table when its rule for smaller inputs is already known. The signals below point to that shape.

signals = [
    "A rule for smaller inputs is already known.",
    "Answers are needed for every size up to a limit.",
    "The same small answers feed many larger ones.",
]
for s in signals:
    print("Signal: " + s)

The tabulation template

The table for climbing stairs starts with the base cases. Each later row adds the two rows below it.

table = [0] * 11
table[0] = 1
table[1] = 1
for i in range(2, 11):
    table[i] = table[i - 1] + table[i - 2]
print("Table:", table)
print("Ways to climb 10 steps:", table[10])

Worked problem: steps of 1, 2, or 3

The table starts with one way for step 0, one way for step 1, and two ways for step 2. Each later row adds the three rows below it.

table = [0] * 9
table[0] = 1
table[1] = 1
table[2] = 2
for i in range(3, 9):
    table[i] = table[i - 1] + table[i - 2] + table[i - 3]
print("Ways to climb 8 steps:", table[8])

Example

nums = [2, 7, 9, 3, 1]
table = [0] * 5
table[0] = nums[0]
table[1] = max(nums[0], nums[1])
for i in range(2, 5):
    table[i] = max(table[i - 1], table[i - 2] + nums[i])
print("Table:", table)
print("Best total:", table[4])

Key points

  • A table is a list that holds one answer per input size.
  • Use the base cases to fill the first rows of the table.
  • Fill later rows by applying the recurrence to earlier rows.
  • Tabulation builds every answer once, from the bottom up.

The table holds the best total up to each house. Each row either skips the house or takes it plus the best total from two houses back. The last row holds 12, from houses worth 2, 9, and 1.

Note

tabulation removes recursion by filling the table in order.

Try it Yourself

Edit the code, then press Run.

Running is simulated · Python Playground

Exercise

In tabulation, which rows of the table are filled first?