Bottom-Up Implementation of Dynamic Programming

Tabulation

Tabulation starts from the bottom and accumulating answers to the top through a table.

The table that the teacher drew is pretty good.

Also see edit distance.

But basically think about the problem in terms of boxes and edges (a sort of graph).

For instance, for the longest common subsequence of 2 strings

Recipe from FreeCodeCamp

1. Visualize the problem as a table
2. Size the table based on inputs
3. Initialize table with default values
4. Seed trivial answers in table
5. Iterate through table, and fill further positions based on current position

Example

Tabulation with Fibonacci problem.

# I haven't tested this so idk if it works
def fibonacci(n):
	table = [0 for i in range(n+1)]
	table[1] = 1
	
	for i in range(2,n+1):
		table[i] = table[i-1] + table[i-2]
	
	return table[n]

Related

• Knapsack DP