Remarks

  • DP is a method for solving optimization problem by breaking the problem into smaller subproblems.
  • DP requires that the overall optimal solution depends on the optimal solution to its subproblems.
  • We might be able to apply DP when:
    1. The subproblems can be seen as smaller version of the original problem.
    2. The optimal solution of a problem is a function of the optimal solutions to one or more of its subproblems.

Two methods using dynamic programming are top-down memoization and bottom up tabulation.

  • Top-down memoization is to recurssivly call the method to find solutions to subproblems and cache the results along the way to avoid redundent calculations.
  • Bottom up tabulation is to solving the smallest subproblem first and then filling up the N dimension optimal solution table.

Classic example for dynammic programming is the fibonacci number calculation.

def fib(n):
    if n <= 1: return 1
    return fib(n - 1) + fib(n - 2)

The recursive relationship here is \(f(n) = f(n - 1) + f(n - 2)\). The above code would work but will be very slow when n increases, due to the redundent calculations in the recursive calls.

With the top down memoization approach, we save the solutions of the subproblems and reuse the reuslts when we don’t need to recalculate.

memo = {0: 1, 1: 1}
def fib_memo(n):
    if n in memo: return memo[n]
    memo[n] = fib_memo(n - 1) + fib_memo(n - 2)
    return memo[n]

With the bottom up tabulation approach, we iterativly fill up the 1 dimensional table up untill we can answer the problem.

def fib_tab(n):
    fibs = [1, 1]
    for i in range(2, n + 1):
        fibs.append(fibs[-1] + fibs[-2])
    return fibs[n]

Sample Questions