Dynamic Programming

Bottom Up
🌀Lecture Flow

● Prerequisites
● What it is
● How to convert top down to bottom up?
● Common Variants
● Common Pitfalls
● Practice Questions
● Quote of the day

2
📋Prerequisites
● DP - Top Down Approach

3
⏰Recap Questions
● What is the Time Complexity of DP in terms of States
○ Imagine you have a DP solution with three states
■ i : 0 < i < 1,000
■ j : 0 < j < 10
■ k: 0 < k < 10

● Is DP brute force? Explain?

● What are problems that have Optimal Substructure, Overlapping
Subproblems and both together?
● What are the three main things we need to figure out with a
top-down approach?

4
⏰Revision: What is DP❓
A method for solving complex problems by breaking them down into
simpler subproblems and reusing solutions to these subproblems to
construct the solution to the original problem.

5
⏰Revision: Use cases
When the problem exhibits the properties of overlapping subproblems and
optimal substructure.

6
What is bottom-up
(tabulation) dp❓

7
⬆What is bottom-up dp?
● Bottom-up DP: Builds from smaller to larger problems.
● Top-down DP: Breaks a larger problem into smaller sub-problems.

Fibonacci

● Bottom-up: dp[i-2] + dp[i-1] known.

● Top-down: dp[i-2] + dp[i-1] initially unknown.

8
🥅Goals
● Has better time-efficiency, we don’t have to pay for recursion.
● Opens doors to memory optimization.

9
󰤃Non-goals
● Better asymptotic time complexity.

10
How do we go from
top-down to bottom-up dp?

11
🍳Recipe: Top-down to bottom-up DP
1. Represent your state-space with some kind of data structure
2. Initialize the base cases in the data structure
3. Figure-out the state transitions.
4. Fill the answers in our data-structure (while respecting the
dependency order).
5. Return the answer for the initial state.

12
509. Fibonacci Number

13
📋Step 1: Represent your state-space.
What would be a good fit?
Array? Matrix?

14
Step 1: Represent your state-space.
An array, right?

dp =[ 0, 1, 1, 2, ..

fib0, fib1, fib2, fib3, ..

15
📋Step 2: Initialize the base cases.
What are the base cases?

16
Step 2: Initialize the base cases.

dp[0] = 0
dp[1] = 1

dp = [0, 1, _, _, _, _, _, …]

17
📋Step 3: Figure-out the state
transitions.
What do you refer when calculating for fib(x)?

18
Step 3: Figure-out the state transitions.
Focus on the dependencies.

dp = [0, 1, 1, 2, 3, 5, 8, …]
0, 1, 2, 3, 4, 5, 6, …

19
📋Step 4: Fill the answers in our array.
But, in what order?

20
Dependency order:
[0, 1] => 2 => 3 => 4 => 5

21
Step 4: Fill the answers in our array.

answers = [0, 1, _ , _ , _ , _ ]
0 1 2 3 4 5

22
Step 4: Fill the answers in our array.

answers = [0, 1, 1 , _ , _ , _ ]
0 1 2 3 4 5

23
Step 4: Fill the answers in our array.

answers = [0, 1, 1 , 2 , _ , _ ]
0 1 2 3 4 5

24
Step 4: Fill the answers in our array.

answers = [0, 1, 1 , 2 , 3 , _ ]
0 1 2 3 4 5

25
Step 4: Fill the answers in our array.

answers = [0, 1, 1 , 2 , 3 , 5 ]
0 1 2 3 4 5

26
📋Step 5: Extract our answer.
Which cell contains our answer?

27
Step 5: Extract our answer.

answers = [0, 1, 1 , 2 , 3 , 5 ]
0 1 2 3 4 5

28
Questions?

29
Let’s do another one.

30
62. Unique Paths

31
⬇Top-down approach
class Solution:
def uniquePaths(self, m: int, n: int) -> int:

@cache
def uniquePathsRec(coord):
row , col = coord
if coord == (m - 1,n - 1):
return 1
ways = 0
if row + 1 < m:
ways += uniquePathsRec((row + 1, col))
if col + 1 < n:
ways += uniquePathsRec((row, col + 1))
return ways

return uniquePathsRec((0,0))

32
Step 1: What does the state space look like?

(0, 0) (0, 1) (0, 2) (0, 3) (0, 4) (0, 5) (0, 6)

(1, 0) (1, 1) (1, 2) (1, 3) (1, 4) (1, 5) (1, 6)

(2, 0) (2, 1) (2, 2) (2, 3) (2, 4) (2, 5) (2, 6)

33
 Step 1: What does the state space look like?

dp =[[ _, _ , _ , _ , _ , _ , _ ]

[ _, _ , _ , _ , _ , _ , _ ]

[ _, _ , _ , _ , _ , _ , _ ]
] 34
 Step 2: What is the base case?

dp =[[ _, _ , _ , _ , _ , _ , _ ]

[ _, _ , _ , _ , _ , _ , _ ]

[ _, _ , _ , _ , _ , _ , 1 ]
] 35
Step 3: What do the moves look like?

36
Step 4: Fill the answers in our array.

9 8 7 6 5 4 3

8 7 6 5 4 3 2

7 6 5 4 3 2 1

37
Order 1: Default

9 8 7 6 5 4 3

8 7 6 5 4 3 2

7 6 5 4 3 2 1

38
Order 2: Row-wise

9 8 7 6 5 4 3

8 7 6 5 4 3 2

7 6 5 4 3 2 1

39
Order 3: Column-wise

9 8 7 6 5 4 3

8 7 6 5 4 3 2

7 6 5 4 3 2 1

40
Step 4: Fill the answers in our array.

28 21 15 10 6 3 1

7 6 5 4 3 2 1

1 1 1 1 1 1 1

41
Base case
Step 5: Extract the answer.

28 21 15 10 6 3 1

7 6 5 4 3 2 1

1 1 1 1 1 1 1

42
󰲐Practice:
N-th Tribonacci Number
Minimum Falling Path Sum

43
⎇Common Variants
● Counting (distinct ways)
○ Usually looks like this: dp[state] = sum(dp[state_1], dp[state_2], dp[..]..)

● Optimization (maximum, minimum, and longest/shortest)

○ Usually looks like this: dp[state] = min/max(dp[state_1], dp[state_2], dp[..]..)

● Decision (yes or no)

○ Usually looks like this: dp[state] = all/any(dp[state_1], dp[state_2], dp[..]..)

44
 Knapsack:
Coin Change II
Solving Questions With Brainpower

45
 DP on Strings:
Is Subsequence
Distinct Subsequences

46
 DP on Grids:
Unique Paths II
Dungeon Game

47
 DP with Bitmask:
Partition to K Equal Sum Subsets
Minimum XOR Sum of Two Arrays

48
Common Pitfalls

49
 Assuming bottom-up dp has better time complexity

● Both bottom-up and top-down DP share the same asymptotic

time complexity.
● Despite this, bottom-up DP is typically more efficient than
top-down DP.

50
 Incorrect Initialization:

def dp(states):
# if we are minimizing, we should use float(‘inf’)
dp = [[0 for _ in range(len)] for i in range(n+1)]

51
 Handling Edge Cases in Bottom-Up DP:

● Edge cases might be overlooked in standard bottom-up DP,

resulting in errors.
● Ensure consideration of smallest, largest, and special input cases
for accurate solutions.

52
Variant to think about:
● States
○ One Index referring to an element in an array
○ Two indices referring to a range in an array
○ Numerical Constraints like do something in k steps
○ Status on whether some action has taken place or not
○ Bitmask/tuple to indicate something is visited or not visited

● Recurrence Relation
○ Static recurrence relation function: fib(n) = fib(n-1) + fib(n-2)
○ Iteration in your recurrence relation

● State Reduction
○ Trying to represent one state in terms of the others

● Context
○ Array
○ Matrix
○ Graph
○ Simulation
53
📚Resources
● Leetcode General Discussion
● Leetcode Explore Card
● Dynamic Programming lecture #1 - Fibonacci, iteration vs recursion
● Competitive Programmer’s Handbook
● Dynamic programming for Coding Interviews: A bottom-up approach to problem
solving
● Traveling Salesperson Problem - DP with Bitmask

54
󰙢Practice Questions
Longest Arithmetic Subsequence of Given Difference
Combination Sum IV
Perfect Squares
Triangle
Solving Questions With Brainpower
Minimum Falling Path Sum
Minimum Path Cost in a Grid
Champagne Tower
55
“We worry top-down, but we invest bottom-up.”

- Seth Klarman

56