There are people out there who like to run long distances for fun.

For fun. It's true.

Anyway, those running-type people start with one step. One step leads to another and another…and another. They just keep putting down those small steps until they add up to something big, like a marathon. (That's about 138,000 feet, if you're counting.)

Bottom-up solutions start small, like that one step. Once they have that small solution, they build on it to create big solutions, but without any literal running. Say we're talking about the Fibonacci sequence again (because that sequence deserves all the love it can get).

Every time you use the Fibonacci sequence, you find the current number by adding together the two numbers in the sequence that came right before it. If you're using variables, it looks something like this:

The n^th Fibonacci number equals the n – 1 Fibonacci number plus the n – 2 Fibonacci number

If you find the solution to the bigger problem by building that equation into a recursive loop, you'll use that optimal sub-problem structure over and over:

Define the Fibonacci function:
	IF n equals 0
		Return 0
	END IF
	IF n equals 1
		Return 1
	END IF
	Return FIBONACCI of n – 1 plus FIBONACCI of n – 2

That's going to get the job done, sure, but our Dynamic Programming senses are tingling, saying that it might not be the best solution. Every time you call the function, it's going to calculate the same starting values over and over. If you need to call it twice, that isn't such a big deal, but what about 15, 100, or 1,000 times? That's a lot of the same calculations and we don't have that kind of time.

Instead, you can rewrite this bottom-up solution to store solutions along the way so that the first time you calculate a new value for FIB(n) is the only time you calculate a value for FIB(n). Then, instead of constantly recalculating values, you can just call things from a list. Here goes...something.

SET an integer array to store the Fibonacci numbers
INITIALIZE 0th and 1st elements of array to account for base cases
 
Define FIBONACCI of n 
	FOR iteration bounds starting at the bottom of tree
		Set array element at current index to sum of prior two Fibonacci numbers
	END FOR
Return nth element of array storing Fibonacci numbers

Whichever way you write the Fibonacci sequence, you're working from the very smallest solution up to the big one, making the solution a—wait for it—bottom-up approach.

Drake would be so proud.