Dissecting Dynamic Programming — Top Down & Bottom Up

Recurrence Relation

“A recurrence relation is an equation that defines a sequence based on a rule that gives the next term as a function of the previous term(s)” (from mathematical perspective)

fib(n) = fib(n-1) + fib(n-2) where fib(0) = 0 and fib(1) = 1

Top Down Approach

Figure #1 — top down subproblem execution order
Figure #2 — Fibonacci top down implementation of fib(n)

Bottom Up Approach

Figure #3 — bottom up approach
Figure #4 — Bottom up implementation of fib(n)

Pros and Cons of Top Down and Bottom Up

--

--

Get the Medium app

A button that says 'Download on the App Store', and if clicked it will lead you to the iOS App store
A button that says 'Get it on, Google Play', and if clicked it will lead you to the Google Play store