Description

Bottom-up DP = fill a table from the base cases up. Each entry is built from earlier ones, iteratively, with no recursion.
?

Reach for when

You have overlapping subproblems you can order so each is solved before it's needed. Pick it to avoid recursion/stack overhead and to enable space optimization (keep only the last row/rows).

Runtime

O(n)

Visualization

!702

Pseudocode

fill out table with answers you know:
table[case1] = answer
table[case2] = answer
for case3 to caseN:
	based on prev answer compute the next
return top of table	

Code

def solve(n): 
	dp = [0] * (n + 1) 
	dp[0] = base # 3. base cases 
	for i in range(1, n + 1): # 4. order: left to right 
		dp[i] = nextAnswer(dp[i - 1], dp[i - 2], ...) # 2. recurrence 
	return dp[n]