Dynamic Programming

Definition:

• In a long function, store a few variables to use it later so that it would take less time

Subproblem with Bellman equation:

• Bellman’s Equation
• Define Opt(j) as the optimal when at j

Recursive Backtracing

• Recurse from n to n-1, …, 1 then backtrack the result

Top-down Dynamic Programming

• Same as Recursive Backtracing with memorization of the value of i that passed through
• Only use with work over-lappting function
• Ex: calculating Fib(n) with O(n)

F[0]=0
F[1]=1
for i in range(2,n):
	F[i] = F[i-1] + F[i-2]
return F[n]

Bottom-up Dynamic Programing

• Tabulation
• Build an array and get solution from bottom up
• backtrack based on the memoization table without explicitly storing values (by checking which case was chosen)
• example: Weighed Interval Scheduling problem:

def sol(j):
	if j==0:
		return []
	elif v_j + M[p(j)] > M[j-1]:
		return [j] union sol(p(j))
	else:
		return sol(j-1)

Bottom-up No-memory Dynamic Programming

• Only remember the last i results to find the next one
• ex: Maximum Subarray Problem:
  • Opt(i)=
    • $x_i\text{if}i=1$
    • $\max (x_i,x_i+Opt(i-1))\text{if}i>1)$
  • Tkae only element $i$ or take element $i$ together with best subarray endding at index $i-1$

Some example problems:

• Subset Sum Problem
• Partition Problem
• Knapsack Problem
• Minimization Knapsack Problem