Dynamic Programming

Dynamic programming has been my nemesis for awhile now and it is about time I tackle dynamic programming using the same approach for dynamic programming.

What is Dynamic Programming

Find out all possible solutions, then pick out best solution.

Recursive in nature.

Principle of Optimality: A problem can be solved by taking a sequence of decisions to get the optimal solution.

Top Down Approach

1. Identify recurrence relation
2. Recursive solution (top-down)
3. Recursive + Memoization (top-down)
4. Iterative + Memoization (bottom-up)
5. Iterative + N variables (bottom-up)

TIP

Fantastic explanation by Abdul Bari on Top Down Approach using Fibonacci example.

Example Solutions

Road Trip

Context

Below is a question I had encountered during one of the technical assessment that tripped me.

You are going on a road trip. You are going to get in your trusty car and drive to Panglossia, where you will spend a nice vacation by the beach. Your car holds C litre of petrol and gets m km per litre. You are handed a list of the n petrol stations are on the road and the price they sell petrol.

Let distance[i] be the distance of the i-th gas station from Start, let cost[i] be the cost of petrol per litre at the i-th station. Furthermore, you can assume that for any two stations i and j, the distance |distance[i] - distance[j]| between them is divisible by m. You start out with an empty tank at station 1. Your final destination is station n.

Hint

Hardest part is identifying the recurrence relation

Recurrence Relation

for each possible i: C(station j, k) = C(station j+1, k - d + i) + cost(station j) * i

C(station j, k): minimum cost to reach destination from station j, with k litre in tank
k: k litre of fuel
d: distance from station j to station j+1
i: amount of fuel topped up

Approach

You can observe that if you have already solved the problem for all j' > j, then it is not hard to compute C(station j, k).

If you start with k litres and it is d km from the next station, then for all i, lookup the already computed C(station j+1, k - d + i), which tells you the minimum cost for arriving at station j+1 with k - d + i litres of petrol. Add this cost per litre at station j times i, and choose the i that is the cheapest.

Work in reverse until you get to the first station, and you will eventually find the cheapest way to reach destination.

Solution

def minimumCost(distance, n, C, cost, m):
  dp = [[0 for i in range(C)] for j in range(n)]
  for j in range(n - 2, -1, -1): # Traverse all stations in reverse
    for k in range(C): # How much fuel in tank starting from station j
      d_next = (distance[j+1] - distance[j]) // m
      min_ = float('inf')
      for i in range(C-k): # How much fuel topped up
        if k + i >= d_next:
          min_ = min(min_, dp[j+1][k - d_next + i] + cost[j] * i)
      dp[j][k] = min_
  print(dp)
  return (dp[0][0])

C = 10 # Capacity of petrol; starts with 0
n = 3
cost = [10,1,1]
d = [0, 20, 100] # distance of ith station from start
m = 10 # km/litre

minimumCost(d, n, C, cost, m)

House Robber

Recurrence Relation

Robber has 2 options: (Knap-sack problems)

• Rob current house
• Don't rob current house

Robber has to maximize profits using these 2 scenarios:

• Rob current house + loot from houses before the previous
• Loot from the previous house and those before that

rob(i) = max(rob(i - 2) + i, rob(i - 1))

Solution

Let rob1 = i - 2 and rob2 = i - 1.

# [rob1, rob2, i, i+1, ...]

def rob(nums):
  rob1 = rob2 = 0
  for i in nums:
    temp = max(rob1 + i, rob2)
    # Shift rob variable forward
    rob1 = rob2
    rob2 = temp
  return rob2

Space Complexity: O(1) as there are always only 2 variables (rob1, rob2) used.

Time Complexity: O(n) as there is only one loop through the nums array.

01 Matrix

tip

Excellent leetcode explanation by hiepit.

Solution 1: DP with Top-Down and Bottom-Up

def updateMatrix(self, mat):
    r, c = len(mat), len(mat[0])
    # Top-Down Approach
    for i in range(r):
      for j in range(c):
        if mat[i][j] > 0: # cells that needs to be updated
          left = mat[i][j-1] if j > 0 else math.inf
          top = mat[i-1][j] if i > 0 else math.inf
          mat[i][j] = 1 + min(left, top)

    # Bottom-Up Approach
    for i in range(r-1, -1, -1):
      for j in range(c-1, -1, -1):
        if mat[i][j] > 0:
          right = mat[i][j+1] if j < c-1 else math.inf
          bot = mat[i+1][j] if i < r-1 else math.inf
          mat[i][j] = min(mat[i][j], 1 + right, 1 + bot)
    return mat

Time Complexity: O(M * N) due to the double for loops to run through the matrix.

Space Complexity: O(1) as no additional data structures were used.

Solution 2: BFS starting from zeroes

def updateMatrix(self, mat):
  DIR = [(0,1), (1,0), (0,-1), (-1,0)]
  queue = []
  for i in range(len(mat)):
      for j in range(len(mat[0])):
        if mat[i][j] == 0:
          queue.append((i, j))
        else:
          mat[i][j] = -1 # marked as not processed

  while queue:
    r, c = queue.pop(0)
    # Check all four directions
    for x, y in DIR:
      nr, nc = r + x, c + y
      # Check out of bounds and already processed
      if nr < 0 or nr >= len(mat) or nc < 0 or nc >= len(mat[0]) or mat[nr][nc] != -1:
        continue
      mat[nr][nc] = 1 + mat[r][c]
      queue.append((nr, nc))

  return mat

Time Complexity: O(M * N) due to the double for loops to run through the matrix.

Space Complexity: O(M * N) due to the queue used.