recursive algorithm is in O(2n) using memoization, you get to O(n)
| Recursive | DP (memoization) |
|---|---|
| Algorithm fib(n): if n=1 or n=2 then return 1 else x := fib(n−1) y := fib(n − 2) return x + y | Algorithm fib(n): new array r[1…n] r[1] := 1 r[2] := 1 for i := 3 to n do r[i] := r[i −1]+r[i −2] return r[n] |
reuse easier sub-problems. order them in way that allows you to reuse them. core of DP: optimal substructures, overlapping subproblems.