Bottom-Up DP with Tabulation
Convert top-down solutions into iterative DP tables, reduce space from O(n) to O(1) where only the last few entries are needed.
Bottom-Up DP with Tabulation is a free DSA Interview Prep lesson on CoddyKit — lesson 3 of 4. You can read the complete lesson below for free — then practise it hands-on in the browser with a built-in code editor and a 24/7 AI tutor. It is part of the DSA Interview Prep learning path, one of 4 lessons in the course, and your progress syncs across the web and the CoddyKit app.
Bottom-Up DP: The Tabulation Approach
Bottom-up DP (tabulation) fills a table of sub-problem answers starting from the smallest sub-problems and building up to the answer. Instead of recursing downward and caching on the way up, you compute iteratively from the ground up. The table is typically a 1D or 2D array where each cell is computed from previously filled cells. This eliminates recursion entirely — no call stack, no recursion limit, and better cache locality.
# Converting top-down to bottom-up:
# Top-down: start at fib(n), recurse to smaller, cache
# Bottom-up: start at fib(0), fill table to fib(n)
# Key question for bottom-up:
# 'In what order do I fill the table so that when I compute dp[i],
# all values dp[i] depends on are already filled?'
# For Fibonacci: dp[i] needs dp[i-1] and dp[i-2]
# Fill order: i = 2, 3, 4, ..., n (left to right)
print('Bottom-up: fill small sub-problems first, build to answer')Bottom-Up Fibonacci
The bottom-up Fibonacci fills dp[0..n] left to right. dp[i] = dp[i-1] + dp[i-2] for i >= 2. Base cases are dp[0] = 0 and dp[1] = 1, stored directly in the array. Time is O(n) and space is O(n) for the full table. Once you see that dp[i] only depends on the last two values, you can reduce space to O(1) with two variables — this is the space optimisation step.
def fib_bottom_up(n):
if n <= 1:
return n
dp = [0] * (n + 1)
dp[0] = 0 # base case
dp[1] = 1 # base case
for i in range(2, n + 1):
dp[i] = dp[i-1] + dp[i-2]
return dp[n]
print([fib_bottom_up(i) for i in range(10)])
# [0, 1, 1, 2, 3, 5, 8, 13, 21, 34]
# Space-optimised to O(1):
def fib_optimised(n):
if n <= 1: return n
a, b = 0, 1
for _ in range(2, n + 1):
a, b = b, a + b
return b
print(fib_optimised(50)) # 12586269025Bottom-Up Coin Change
For coin change, the bottom-up table is dp[0..amount], where dp[i] = minimum coins to make amount i. Initialise dp[0] = 0 (zero coins for zero amount) and dp[1..amount] = infinity. For each amount i from 1 to target, try each coin: if i >= coin, then dp[i] = min(dp[i], 1 + dp[i - coin]). The answer is dp[amount], or -1 if still infinity.
def coin_change(coins, amount):
dp = [float('inf')] * (amount + 1)
dp[0] = 0 # base case: 0 coins for amount 0
for i in range(1, amount + 1):
for coin in coins:
if i >= coin: # can use this coin
dp[i] = min(dp[i], 1 + dp[i - coin])
return dp[amount] if dp[amount] != float('inf') else -1
print(coin_change([1, 5, 6, 9], 11)) # 2: (5+6)
print(coin_change([2], 3)) # -1: impossible
print(coin_change([1, 2, 5], 11)) # 3: 5+5+1
print(coin_change([186, 419, 83, 408], 6249)) # 20Fill Order: The Critical Insight
The fill order is the heart of bottom-up DP. For any state dp[i], all states it depends on must be computed first. For 1D DP where dp[i] depends on dp[i-1] and dp[i-2], fill left to right. For 2D DP where dp[i][j] depends on dp[i-1][j] and dp[i][j-1], fill row by row (top to bottom, left to right). Always draw the dependency arrows before coding to confirm the fill order.
# Fill order examples:
# 1D: dp[i] = f(dp[i-1], dp[i-2])
# Arrows point LEFT: fill LEFT TO RIGHT
# i: 0 -> 1 -> 2 -> ... -> n
# 2D: dp[i][j] = f(dp[i-1][j], dp[i][j-1])
# Arrows point LEFT and UP: fill TOP-LEFT TO BOTTOM-RIGHT
# Fill row 0 first, then row 1, etc.
# 2D reversed: dp[i][j] = f(dp[i+1][j], dp[i][j+1])
# Arrows point RIGHT and DOWN: fill BOTTOM-RIGHT TO TOP-LEFT
# Used in interval DP and some string problems
print('Draw dependencies first, then determine fill order')Bottom-Up LCS: 2D Table
The Longest Common Subsequence bottom-up table is (m+1) × (n+1), where dp[i][j] = LCS of s1[:i] and s2[:j]. Base cases: dp[0][j] = dp[i][0] = 0 (empty string has LCS 0 with anything). Fill row by row: if s1[i-1] == s2[j-1], dp[i][j] = 1 + dp[i-1][j-1]; else dp[i][j] = max(dp[i-1][j], dp[i][j-1]). The answer is dp[m][n].
def lcs_bottom_up(s1, s2):
m, n = len(s1), len(s2)
# (m+1) x (n+1) table, initialised to 0
dp = [[0] * (n + 1) for _ in range(m + 1)]
for i in range(1, m + 1):
for j in range(1, n + 1):
if s1[i-1] == s2[j-1]: # characters match
dp[i][j] = 1 + dp[i-1][j-1]
else: # skip one character
dp[i][j] = max(dp[i-1][j], dp[i][j-1])
return dp[m][n]
print(lcs_bottom_up('abcde', 'ace')) # 3
print(lcs_bottom_up('ABCBDAB', 'BDCAB')) # 4: 'BCAB' or 'BDAB'Space Optimisation: Rolling Array
Many 2D DP tables can be reduced to 1D (or 2 rows) by observing that dp[i][j] only depends on the current row and the previous row. Keep two arrays: prev and curr, or update a single array in the right order. For LCS, dp[i][j] depends on dp[i-1][j], dp[i][j-1], and dp[i-1][j-1] — keeping just the previous row suffices.
def lcs_space_optimised(s1, s2):
m, n = len(s1), len(s2)
# Keep only one row (previous row state)
prev = [0] * (n + 1)
for i in range(1, m + 1):
curr = [0] * (n + 1)
for j in range(1, n + 1):
if s1[i-1] == s2[j-1]:
curr[j] = 1 + prev[j-1] # dp[i-1][j-1]
else:
curr[j] = max(prev[j], curr[j-1]) # dp[i-1][j] and dp[i][j-1]
prev = curr
return prev[n]
print(lcs_space_optimised('abcde', 'ace')) # 3
# Space: O(n) instead of O(mn)Bottom-Up House Robber
House robber bottom-up fills dp[0..n-1] where dp[i] = maximum profit robbing houses 0 through i. dp[0] = nums[0], dp[1] = max(nums[0], nums[1]), and for i >= 2: dp[i] = max(dp[i-1], dp[i-2] + nums[i]). Since dp[i] only depends on the last two values, this immediately space-optimises to O(1) with two variables — a common pattern for 1D DP with two-step dependencies.
def rob_bottom_up(nums):
if not nums: return 0
if len(nums) == 1: return nums[0]
# Full table version: O(n) space
dp = [0] * len(nums)
dp[0] = nums[0]
dp[1] = max(nums[0], nums[1])
for i in range(2, len(nums)):
dp[i] = max(dp[i-1], dp[i-2] + nums[i])
return dp[-1]
def rob_optimised(nums):
# O(1) space: only need last two values
if not nums: return 0
if len(nums) == 1: return nums[0]
prev2, prev1 = nums[0], max(nums[0], nums[1])
for i in range(2, len(nums)):
prev2, prev1 = prev1, max(prev1, prev2 + nums[i])
return prev1
print(rob_optimised([2, 7, 9, 3, 1])) # 12Minimum Path Sum in a Grid
Minimum Path Sum (LeetCode #64): find a path from top-left to bottom-right minimising the sum of values (you can only move right or down). 2D DP: dp[i][j] = minimum sum to reach cell (i,j). dp[i][j] = grid[i][j] + min(dp[i-1][j], dp[i][j-1]). Fill left-to-right, top-to-bottom. Base case: dp[0][0] = grid[0][0], first row fills right-only, first column fills down-only.
def min_path_sum(grid):
rows, cols = len(grid), len(grid[0])
dp = [[0] * cols for _ in range(rows)]
dp[0][0] = grid[0][0]
# Fill first row (can only come from left)
for c in range(1, cols):
dp[0][c] = dp[0][c-1] + grid[0][c]
# Fill first column (can only come from above)
for r in range(1, rows):
dp[r][0] = dp[r-1][0] + grid[r][0]
# Fill rest of the table
for r in range(1, rows):
for c in range(1, cols):
dp[r][c] = grid[r][c] + min(dp[r-1][c], dp[r][c-1])
return dp[rows-1][cols-1]
grid = [[1,3,1],[1,5,1],[4,2,1]]
print(min_path_sum(grid)) # 7: 1+3+1+1+1Modifying the DP Table In-Place
When extra space is forbidden, you can sometimes modify the input grid itself as the DP table. For minimum path sum, overwrite grid[i][j] with the minimum cost to reach that cell. This uses O(1) extra space but destroys the input — always mention this trade-off to the interviewer and confirm it is acceptable. If the input must be preserved, use the rolling-array approach instead.
def min_path_sum_inplace(grid):
rows, cols = len(grid), len(grid[0])
# Modify grid in-place (O(1) extra space, destroys input)
for r in range(rows):
for c in range(cols):
if r == 0 and c == 0:
continue # starting cell
elif r == 0:
grid[r][c] += grid[r][c-1] # first row
elif c == 0:
grid[r][c] += grid[r-1][c] # first column
else:
grid[r][c] += min(grid[r-1][c], grid[r][c-1])
return grid[rows-1][cols-1]
import copy
grid = [[1,3,1],[1,5,1],[4,2,1]]
print(min_path_sum_inplace(copy.deepcopy(grid))) # 7Comparing Top-Down and Bottom-Up on Coin Change
Both approaches solve coin change optimally but differ in practice. Top-down is cleaner to write and only computes sub-problems that are actually reachable. Bottom-up computes all amounts from 0 to target, even those unreachable with the given coins (which remain at infinity). For sparse problems (few reachable states), top-down is more efficient; for dense problems, bottom-up has lower overhead.
import functools
# Top-down: only computes reachable amounts
def coin_change_top(coins, amount):
@functools.lru_cache(maxsize=None)
def dp(rem):
if rem == 0: return 0
if rem < 0: return float('inf')
return 1 + min(dp(rem - c) for c in coins)
r = dp(amount)
return r if r != float('inf') else -1
# Bottom-up: computes all amounts 0 to target
def coin_change_bottom(coins, amount):
dp = [float('inf')] * (amount + 1)
dp[0] = 0
for i in range(1, amount + 1):
for c in coins:
if i >= c: dp[i] = min(dp[i], 1 + dp[i-c])
return dp[amount] if dp[amount] != float('inf') else -1
print(coin_change_top([1,5,6,9], 11)) # 2
print(coin_change_bottom([1,5,6,9], 11)) # 2Unique Paths: Classic 2D DP
Unique Paths (LeetCode #62) counts the number of paths from the top-left to the bottom-right of an m×n grid, moving only right or down. The recurrence is straightforward: dp[i][j] = dp[i-1][j] + dp[i][j-1] — paths from above plus paths from the left. Base cases: the entire first row and first column each have exactly 1 path (only one direction to travel). This 2D DP fills in O(mn) time and can be reduced to O(n) space with a rolling row.
def unique_paths(m, n):
# dp[i][j] = number of paths to reach cell (i,j)
dp = [[1] * n for _ in range(m)]
# Base: first row and first column are all 1
for i in range(1, m):
for j in range(1, n):
dp[i][j] = dp[i-1][j] + dp[i][j-1]
return dp[m-1][n-1]
print(unique_paths(3, 7)) # 28
print(unique_paths(3, 2)) # 3
# O(n) space rolling row:
def unique_paths_opt(m, n):
row = [1] * n
for _ in range(1, m):
for j in range(1, n):
row[j] += row[j-1]
return row[n-1]
print(unique_paths_opt(3, 7)) # 28Quick Check
Test your understanding of Data Structures & Algorithms — Coding Interview Prep concepts from this lesson.
Lesson Recap
In this lesson you learned: bottom-up DP with tabulation and how to determine the fill order from dependency arrows, space optimisation using rolling arrays (O(mn) to O(n)) and two-variable tracking (O(n) to O(1)), and bottom-up implementations of Fibonacci, coin change, LCS, house robber, and minimum path sum. Next up we solve the coin change and min-cost staircase problems end to end.
Frequently asked questions
Is the “Bottom-Up DP with Tabulation” lesson free?
Yes — the full text of “Bottom-Up DP with Tabulation” is free to read here on the web, and the DSA Interview Prep course includes 4 lessons in total. To practise it interactively (a built-in code editor and a 24/7 AI tutor) and unlock the rest of the DSA Interview Prep course, upgrade to CoddyKit PRO.
What will I learn in “Bottom-Up DP with Tabulation”?
Convert top-down solutions into iterative DP tables, reduce space from O(n) to O(1) where only the last few entries are needed. You practise DSA Interview Prep with hands-on code you run directly in the browser, and a 24/7 AI tutor answers your questions as you work through the lesson.
Do I need any experience to start DSA Interview Prep?
No prior experience is required. DSA Interview Prep on CoddyKit is structured for beginners through advanced learners; this is — lesson 3 of 4, so you can start here or from the beginning and move at your own pace.
How long does the “Bottom-Up DP with Tabulation” lesson take?
Most CoddyKit lessons take about 5–10 minutes. Each one is bite-sized and interactive, so you make steady progress and pick up exactly where you left off across the web and the app.
Can I write and run code in this DSA Interview Prep lesson?
Yes. Every DSA Interview Prep lesson includes a built-in code editor, so you write and run real code right in your browser and get instant AI feedback — no local setup required.
All lessons in this course
- Recognising DP: Overlapping Sub-Problems
- Top-Down DP with Memoisation
- Bottom-Up DP with Tabulation
- Coin Change and Min-Cost Staircase