Dynamic programming (DP) is a way to solve algorithmic problems with overlapping subproblems. Algorithms using DP find the base case and building a solution from the ground-up. Dp keep track of previous results to avoid re-computing the same operations.
*Write down 1+1+1+1+1+1+1+1+1+1*
— What’s that equal to?
— *Kid counting one by one* Ten!
— Add another "+1". What’s the total now?
— *Quickly* Eleven!
— Why you get the result so quickly? Ah, you got it faster by adding one to the memorized previous answer. So Dynamic Programming is a fancy way of saying: "remembering past solutions to save time later."
Let’s solve the same Fibonacci problem but this time with dynamic programming.
When we have recursive functions, doing duplicated work is the perfect place for dynamic programming optimization. We can save (or cache) the results of previous operations and speed up future computations.
link:../../../src/algorithms/fibonacci-dynamic-programming.js[role=include]This implementation checks if we already calculated the value, if so it will save it for later use.
graph G {
"fib(5)" -- { "fib(4)" }
"fib(4)" -- { "fib(3)" }
"fib(3)" -- { "fib(2)" }
"fib(2)" -- { "fib(1)", "fib(0)" }
}
This graph looks pretty linear now. It’s runtime O(n)!
TIP: Saving previous results for later is a technique called "memoization". This is very common to optimize recursive algorithms with overlapping subproblems. It can make exponential algorithms linear!