Chapter 12 — Dynamic Programming

Dynamic programming

Avoiding repeated work in recursive-style problems

Recursive speed trap

Recursive code gets slow by repeating the same calculations

Overlapping subproblems

The same smaller problem is solved repeatedly

Fix repeated recursion

Store the recursive result and reuse it

Bad recursive max

Can become O(2^N) if it repeats recursive calls

Improved recursive max

O(N), if each element is processed once

Fibonacci sequence

Each number is the sum of the previous two numbers

Recursive Fibonacci problem

It repeats many of the same calculations

Recursive Fibonacci Big O

O(2^N)

Memoization

Saving previously computed results

Memoization storage

Usually a hash table

Memoized Fibonacci Big O

O(N)

Bottom-up dynamic programming

Solves from the smallest case upward using iteration

Memoization vs bottom-up

Memoization improves recursion; bottom-up avoids recursio