Tabulation (Bottom-Up DP)

DSA · Dynamic Programming

Theory

Tabulation solves a dynamic programming problem by filling a table iteratively, starting from the smallest subproblems and building up to the answer. Instead of recursion, you decide an order in which every subproblem's dependencies are already computed, then loop through that order. For Fibonacci, table[0] = 0, table[1] = 1, and each later cell is the sum of the two before it. Because there is no recursion, there is no stack overflow risk and no function-call overhead, and you can often reduce memory by keeping only the last few rows or values. The steps are always the same: define what table[i] means, write the recurrence, set base cases, choose the fill order, and read the final answer from the table.

Why we use it

Bottom-up DP is usually faster than memoised recursion, avoids recursion depth limits, and makes space optimisation (keeping only what is needed) straightforward.

When to use it

Use tabulation when you will need most subproblems anyway, when inputs are large enough that recursion could overflow, or when you want to optimise memory.

How it works

  1. Create table with base cases
  2. For each state in dependency order
  3. table[state] = recurrence(earlier states)
  4. Return the final cell

Syntax

table = [base values]
for i in fill order:
    table[i] = recurrence(table[smaller i])
return table[target]

Example

# 1. Fibonacci with a table, then with O(1) memory
def fib_table(n):
    t = [0, 1] + [0] * (n - 1)
    for i in range(2, n + 1):
        t[i] = t[i - 1] + t[i - 2]
    return t[n]

def fib_two_vars(n):
    a, b = 0, 1
    for _ in range(n):
        a, b = b, a + b
    return a

print(fib_table(50), fib_two_vars(50))

# 2. Minimum cost path in a grid (move right or down)
cost = [
    [1, 3, 1],
    [1, 5, 1],
    [4, 2, 1],
]
R, C = len(cost), len(cost[0])
dp = [[0] * C for _ in range(R)]
for r in range(R):
    for c in range(C):
        if r == 0 and c == 0:
            dp[r][c] = cost[r][c]
        else:
            up = dp[r - 1][c] if r else float("inf")
            left = dp[r][c - 1] if c else float("inf")
            dp[r][c] = cost[r][c] + min(up, left)
for row in dp:
    print(row)
print("Minimum path cost:", dp[-1][-1])

Key points

DSA topics

Introduction to DSA

Arrays and Searching

Sorting Algorithms

Linked Lists

Stacks and Queues

Hashing

Trees

Heaps

Graphs

Algorithm Techniques

Classic Algorithms

Dynamic Programming

T
Tech Town
Log InSign Up Free
Home SQL Python DSA Power BI Snowflake Databricks Spark Gen AI Practice Problems Contest Blog

Data Structures & Algorithms

The complete DSA roadmap: theory, why and when to use every structure and algorithm, Big O complexity, and Python code you can run right here in the browser.

{{ sectionCount }}
Sections
{{ topicCount }}
Topics
Free
Forever
Hands-on practice Practice DSA Online 251 problems across 13 patterns, with hidden tests and step-by-step optimal solutions. Start practising →
Section {{ sec.num }}

{{ sec.label }}

DSA  /  {{ current.sectionLabel }}  /  {{ current.name }}

{{ current.name }}

Theory

{{ current.def }}

Why we use it

{{ current.why }}

When to use it

{{ current.when }}

Flowchart — how {{ current.name }} works
{{ nd.text }}
{{ nd.text }}
◇ {{ nd.text }}
Yes → {{ nd.yes }}
No → {{ nd.no }}
Step-by-step visualisation
{{ cell.v }}
{{ cell.i }} {{ cell.tag }}
Step {{ vizStepLabel }}: {{ vizNote }}
■ comparing ■ swapping / moving ■ done / found ■ out of range
Complexity & Pseudocode
{{ current.syntax }}
Example Code
{{ current.example }}
▶ Try It Live — runs real Python 3 in your browser (first run loads the engine)
{{ liveOutput }}
{{ liveError }}
Key Points — click to check off as you learn
  • {{ pt.mark }} {{ pt.text }}

Share this topic