31 What is dynamic programming ?

• Very different from greedy algorithms
  • Greedy algorithms decide a rule and follow it blindly
  • Dynamic programming studies the problem more carefully
• Solve the problem by building up solution from sub-problems
  • How to choose which sub-problems to consider ?
  • How to combine answers of sub-problems to solve the given problem ?
• Dynamic programming might seem like we are actually doing brute-force search
  • But analysis will show we are doing much better

Fibonacci Numbers

$$\begin{array}{rl}\text{Algorithm }\mathrm{RecursiveFibonacci}(n)& \\ 1:& \text{If }n=0\text{ return }0\\ 2:& \text{If }n=1\text{ return }1\\ 3:& \text{Otherwise return }\mathrm{RecursiveFibonacci}(n-1)+\mathrm{RecursiveFibonacci}(n-2)\end{array}$$

Fibonacci Numbers: Memoization of recursion

To compute $F_n$ via $\mathrm{RecursiveFibonacci}(n)$, we need

• one recursive call to $\mathrm{RecursiveFibonacci}(n-1)$
• two recursive calls to $\mathrm{RecursiveFibonacci}(n-2)$
• $\cdots$ Instead of computing these Fibonacci numbers from scratch each time, can’t we just remember them to look up later as needed ?

Algorithm $\mathrm{MemoizationFibonacci}(n)$

$$\begin{array}{rl}1:& \text{If }n=0\text{ return }0.\text{If }n=1\text{ return }1\\ 2:& \text{if }F[n]\text{ is undefined then}\\ 3:& F[n]\leftarrow \mathrm{MemoizationFibonacci}(n-1)+\mathrm{MemoizationFibonacci}(n-2)\\ 4:& \text{end if}\end{array}$$

Trimming the recursive tree to compute $F_7$ via memoization. Downward green arrows indicate writing into the memoization array & upward red arrows indicated reading from the memoization array.

Fibonacci Numbers (Intentionally filling up the array!)

Algorithm $\mathrm{IterativeFibonacci}(n)$

$$\begin{array}{rl}1:& F[0]\leftarrow 0\\ 2:& F[1]\leftarrow 1\\ 3:& \text{for }i\leftarrow 2\text{ to }n\text{ do}\\ 4:& F[i]\leftarrow F[i-1]+F[i-2]\\ 4:& \text{end for}\end{array}$$

Analysis of Running time

• We store $n$ numbers in the array $F$
• Computing each new entry needs to look up two known numbers and perform one addition
• Hence, total running time to compute $F_n$ is $O(n)$