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 Coding Interview Prep lesson on CoddyKit. This is 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 Coding Interview Prep learning path, and your progress syncs across the web and the CoddyKit app. The Coding Interview Prep course includes 4 lessons in total.
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.
Learn Coding Interview Prep with an AI tutor — free
Write and run real code in your browser, get instant help from a 24/7 AI tutor, and pick up where you left off on the web or in the app.
- Courses
- 90
- Lessons
- 360
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. To practise it interactively (a built-in code editor and a 24/7 AI tutor) and unlock the rest of the Coding Interview Prep course, upgrade to CoddyKit PRO. The Coding Interview Prep course includes 4 lessons in total.
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 Coding 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 Coding Interview Prep?
No prior experience is required. Coding Interview Prep on CoddyKit is structured for beginners through advanced learners, so you can start here or from the beginning and move at your own pace. This is lesson 3 of 4.
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 Coding Interview Prep lesson?
Yes. Every Coding 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