Dynamic programming isn't for the faint of heart. It's a solution for all of those problems that could take up way too much of the CPU's time to be affordable. If you have a solution that takes an exponential amount of time (yikes) or an unknown number of iterations (even more yikes), you'll want to use dynamic programming to minimize that CPU time.

Sounds scary, we know, but it's actually a pretty straightforward approach.

If you can break the problem down into the substructure of an optimal solutions, then piece together the solutions to the sub-problems, you can create a bottom-up solution that doesn't cause your computer to meltdown.

If you don't have optimal solutions for your subproblems, you can't use a greedy algorithm. A greedy algorithm is going to pick the first solution that works, meaning that if something better could come along later down the line, you won't see it.

That's the beauty of a dynamically-programmed solution, though. It's going to let you look at all the possible solutions (through memorization) so that you can find the best solution.

Wait, what? Let's look at an example.

Say you're packing your suitcase to go on your dream vacation to the South Pole. How did we know it's your dream vacation? It's everybody's dream vacation. Between sliding with penguins and taking everything you came with home with you (in one form or another), there's no reason not to want to go there.

Before you get there, though, you'll need to pack as many thermal outfits as possible without exceeding the airline's weight limit on your bag (meaning you'd have to pay another fee). You have to be efficient in your packing.

Like many other dynamic programming solutions, this one means you'll be using—wait for it—recursion. If recursion's new to you, you'll want to take a look at that page real quick. We'll wait.

Got it? Good.

Before you start solving, you're going to need a couple of things for this knapsack problem. (That's what it's called most of the time: the knapsack problem.) You'll need to know

• the capacity of your knapsack, which we'll call MaxSize. This is completely weight-based; we'll assume if it fits in the weight limit, your combination of clothes can fit in the bag (even if it takes some jumping on the suitcase to make things work).
• a list of possible clothes to take, called Clothes[].
• a list telling you how much each piece of clothing weighs, called ItemWeight[].
• a list telling you have much each piece of clothing is worth, called Value[].
• counter n to work your way through the array, keeping track of how many things have gone in the knapsack without breaking the capacity.

You'll know you've found the solution if it gives the maximum number of clothes you can put in a knapsack while still fitting in the capacity's weight limit. Did you see the keyword in there? You're looking for the maximum, which means you're looing to optimize in your solution. Optimization means that dynamic programming is the way to go.

Here are the lists you'll need:

Let's say you can only bring a carry-on to Antarctica with a limit of 10 pounds. To simplify the problem a tad, we're also going to say you've only got one of each item. the goal is to stuff as much value into the luggage as possible without maxing out the weight. When we say "value," we're talking about how much each item's worth to you in Antarctica. Even if you got your snow jacket at the bargain bin of GoodWill, it's going to be infinitely more valuable to you in Antarctica than a gold-lined Speedo from Nieman Marcus.

Working Through the Algorithm

DEFINE MaxValueFunction(MaxSize, Clothes[], ItemWeight[], Value[])
	/*2D List to store running values*/
	INTIALIZE ValArray[][] to length of Clothes rows and MaxSize columns
	
	FOR i in range ValArray rows
		FOR j in range ValArray columns
			IF i or j is 0
				ValArray[i][j] = 0			/*If the item weighs less than the maximum of the current bag weight */
			ELSE
				/*value without adding the item*/
				prevVal = ValArray[i][j-1]
 
				/*value without adding the item to the list above it*/
				aboveVal = ValArray[i-1][j]
 
				/*value after adding the item*/
				itemVal = ItemWeight[j-1]
 
				addingItemVal = ValArray[i-1][j – itemWeight]
 
				valAddedIn = max(prevVal, aboveVal, addingItemVal)			ValArray[i][j] = valAddedIn
	returnValArray
END Function

If you use that function to figure out the best items to bring to Antarctica, you'll end up with this:

To figure out the best packing strategy, this algorithm starts by checking each item against a weight limit of 0 and works its way up to 10. As each piece of clothing becomes something that isn't heavier than the weight limit, the algorithm starts checking whether or not it can add the item from three sides:

• the top without adding it.
• the left without adding it.
• the diagonal after adding it.

If the combination with the most value has already happened, that's how the algorithm checks those options. Otherwise, it's going to add in the item and count it towards the new best weight.

Say you're looking at adding in the jacket after figuring out when you can add the snow pants. Here's the table so far:

Up until the weight limit was 7, thermal underwear has been the only thing that could fit in the suitcase. Now that we've reached the point where we could add in the snow pants, though, we need to check three spots:

• If the snow pants have more value on their own
• If the thermal underwear has more value on its own
• If we can put both in the suitcase

If the first is true, then the number to the top is going to be more. If the second is true, the number to the left is going to be more. If the third option works, we'll have to go up a row and check the weight of the thermal underwear to check. Since we're at weight 7, to have both thermals and the snow pants, the snow pants are going to have to weigh 5 or less and…they don't. That means for now the snow pants win.

In fact, we won't be able to have both until hitting a bag weight limit of 9, like this:

Looks good. That wasn't so bad.

Now that we've gotten all the way through a dynamic programming optimization problem, let's do a quick review of the key takeaways: 

1. The key to finding a DP solution is to express a large problem in terms of smaller problems that have optimal substructures. 
2. Avoid the wiles of the greedy algorithm by planning to solve all the sub-problems so you can evaluate each, then piece them together as you need to determine the best solution to the larger problem. 
3. Memoize your solutions so that you can minimize the time your CPU spends thinking about the same exact calculations.

That's it. You should now know everything there is to know about dynamic programming.

Or at least you know enough to be dangerous.