DP

Dynamic Programming

video

==DP = recursion + memorization = local brute force==

DP is useful for building solution to unknown problems

Steps for building a DP from stratch

• Find subproblem
• Find the relationship between subproblem and the original problem ( A recurrence equation)
• solve the subproblems via recursion
• Topological sort the subproblems and give an order of sovling them
• Solve the original problem via solving subproblems at the given order

Components

• Subproblem
• Relation
• Topological order
• Base case
• Original problem
• Time complexity

Big IDEA : memorization

Remeber and Reuse the solution to subproblem

• Map subproblem to their solutions
• Before solving subproblems check if they are solved already
• If not solved yet, solve it and store the solution

memo = {}
if subp in memo:
    return memo[subp]
else:
    res = solve(supb)
    memo[subp] = res
    return res

• Time complexity is less than sum(O(subproblems)), since each subproblem only need to be solved once.

Example : Fibonacci

Duplication found ! We should memorize the result and avoid recomputation

# Simple recursion
def Fib(n):
    if n == 1 or n == 2: return 1
    else: return Fib(n-1) + Fib(n-2)

# DP solution
memo = {}
memo[1] = 1
memo[2] = 1
def Fib(n):
    if n in memo:
        return memo[n]
   	else:
        res =  Fib(n-1) + Fib(n-2)
        memo[n] = res
        return res

Usual Subproblems for a sequence l

• Prefix : l[:i]
• Suffix : l[i:]
• Substrings : l[i:j]
• Divide : l[:len(l)//2] + l[len(l)//2:]
• …

Usual Subproblems for multiple sequences

Apply usual subproblems for every sequence

Turn recursion to iteration

Bottom-up DP

• Your base case as the start of iteration
• The topological order as a for or while loop
• The relationship between your subproblem and the original problem(the recursion equation)
• return your result.

Example : LCS

• Subproblem : LCS(A[i:] , B[j:])

• Relation :

  if A[i] == B[j]:
      return 1 + LCS(A[i+1:],B[j+1:])
  else:
      return max([LCS(A[i+1:],B[j:]) , LCS(A[i:] , B[j+1:])])

• Topological : for i in range(len(A)) , for j in range(len(B))

• Base : LCS([],[]) == 0

Parent Pointer