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: 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)) # 12586269025All 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