Summer’s over — what’s your move? Join Pro for 50% off using code [MAKEITHAPPEN](https://www.codecademy.com/checkout?periods=year&plan_id=proGoldAnnualV2&discountCode=MAKEITHAPPEN)


Improve the runtime efficiency of your algorithms by applying dynamic programming. Break down problems, store their sub-answers, and recombine the stored computations to dramatically improve your problem-solving ability.

Technical Interview Problems: Dynamic Programming

With our grid built, we only need to fill it in to find our optimal value. Remember: each column is the capacity of a knapsack and each row is an item we can add. The first row is "no item" and the first column is "no capacity".

We'll consider the diamond first. It weighs 1 pound and is worth $7. For each capacity after 0 (our first column), we can place the diamond in that location. Some capacities have spare weight, but that's okay.
```py
           # Capacity: 0| 1| 2| 3| 4|
#____________________________________
# first row: no item! [0, 0, 0, 0, 0]
# second row: Diamond [0, 7, 7, 7, 7]
```

Let's add a trophy worth $6 and weighing 2 lbs.

The trophy **doesn't fit in a 1lb. knapsack**, so we look at the **previous row** and fill this section with that value.

```py
           # Capacity: 0| 1| 2| 3| 4|
#____________________________________
# first row: no item! [0, 0, 0, 0, 0]
# second row: Diamond [0, (7), 7, 7, 7]
# third row: Trophy   [0, (7), ?, ?, ?]
```

The trophy fits in the 2lb. knapsack; we have two options: 

1. Trophy plus **value stored at the remaining weight**
2. The **previous best** in the 2lb. sub-knapsack.

Adding the 2 lb. trophy would mean 0 remaining capacity. This is why "no capacity", "no item" values live in our grid.

Option 1 = 6 (trophy value) + 0 ("no capacity" value)

Option 2 = 7 (the previous best)

By weighing our options, we see this section should store the diamond value **even though there's spare weight**. We're maximizing for value!

```py
           # Capacity: 0| 1| 2| 3| 4|
#____________________________________
# first row: no item! [0, 0, 0, 0, 0]
# second row: Diamond [0, 7, 7, 7, 7]
# third row: Trophy   [0, 7, 7, ?, ?]
```

We repeat this process with the 3lb. sub-knapsack: 

Option 1 = 6 (trophy value) + 7 (1lb. sub-knapsack value)
Option 2 = 7 (the previous best)

```py
           # Capacity: 0| 1| 2| 3| 4|
#____________________________________
# first row: no item! [0, 0, 0, 0, 0]
# second row: Diamond [0, 7, 7, 7, 7]
# third row: Trophy   [0, 7, 7, 13, ?]
```

One last time for the 4lb. knapsack:

Option 1 = 6 (trophy value) + 7 (2lb. sub-knapsack value)
Option 2 = 7 (the previous best)

```py
           # Capacity: 0| 1| 2| 3| 4|
#____________________________________
# first row: no item! [0, 0, 0, 0, 0]
# second row: Diamond [0, 7, 7, 7, 7]
# third row: Trophy   [0, 7, 7, 13, 13]
```

Note that the best value is stored in our bottom-right section. This is true no matter how many items we add.

The order we consider items is irrelevant for the final value. Here's how the grid would look trophy-first:

```py
           # Capacity: 0| 1| 2| 3| 4|
#____________________________________
# first row: no item! [0, 0, 0, 0, 0]
# second row: Trophy  [0, 0, 6, 6, 6]
# third row: Diamond  [0, 7, 7, 13, 13]
```



Knapsack With Memoization: Filling in the Grid

Dynamic programming is a technique to optimize solutions for problems which have a structure that involves repeated, identical computations. 

For dynamic programming to work, it's essential that the problem can be **broken into overlapping sub-problems** which combine into a solution for the original problem.

Dynamic programming requires us to store the answers to sub-problems so they can be retrieved as components to larger solutions. We memoize the solutions by storing them inside a data structure with efficient look-up.

While dynamic programming can be tricky to master, it's an essential tool for optimizing many useful algorithms. The key idea is to break the problem down, solve each sub-problem, and combine the sub-answers. 


The difficulty lies in how the problem is broken apart, how the sub-answers are stored, and how they're used to solve the original problem.

For Fibonacci, we stored the previous numbers so we did not need to recompute them.

For Knapsack, we stored which items gave us the best value for every size knapsack. Then we could efficiently retrieve the best option whenever adding a new item.


Dynamic Programming Review

Dynamic programming is an optimization strategy for designing algorithms. The technique is beneficial for technical interviews because solving problems with an optimal big O runtime will improve your chances of being hired.

We'll describe dynamic programming with a question: What is `1 + 1 + 1 + 1`?

Now, what is one more, or `1 + 1 + 1 + 1 + 1`? 

For the first question, you counted each `1` to arrive at `4`, but for the second question, you only needed to add `1` to the previous total. You "stored" the previous sum to avoid a calculation already performed.

That's dynamic programming! Break a problem into smaller sub-problems, store the answers to the sub-problems, and use those stored answers to solve the original problem.

We need _overlapping sub-problems_ for the stored answers to be useful; answers for overlapping sub-problems are **consistent and relevant to the original problem**. 

With a linear search, we examine each element in a collection to find a target element. We can't apply dynamic programming because there is no overlapping sub-problem. An element's location can vary between searches and the location in one search has no relevance to another search in a larger collection.


Introduction to Dynamic Programming

Our brute force approach is inefficient! We're compounding work by creating many different combinations that contain the same items. Just like with Fibonacci, we're repeating computations that won't change.

With the Fibonacci Sequence, we had one variable to store: the number itself. We could place that number in a Python dictionary and look it up as needed.

Now we're dealing with multiple variables: the item's weight and value as well as the capacity of the knapsack. A dictionary's key-value pairs won't be sufficient to store all the answers to our subproblems. 

We'll start tackling this problem by building a grid which **can** store all our sub-answers. 

The **columns** of our grid represent **each possible capacity** up to the weight limit. 

The **rows** of our grid represent **each possible item** we can fit into a knapsack.

Why do we want each possible capacity? Because finding the optimal capacity for a knapsack of weight `4` will be much more efficient if we already know the optimal capacities for knapsacks of weight `3` and `1`!

Knapsack With Memoization: Building the Grid

Dynamic programming is especially helpful for problems where there are many different options and we have a particular goal we're trying to maximize.

For the sake of learning, we're going to imagine ourselves as burglars. We've broken into someone's home and there are many different things we can steal. 

Each item has a weight and a value. Our goal is to maximize the total value of items while remaining within the weight we can fit in our knapsack.

This is another ideal situation to apply dynamic programming, but to start we'll use the _brute force_ approach and **generate every single possible combination.**

We can total each combination's weight and value to find the most lucrative collection.

To help, we're given a `Loot` class with `name`, `weight`, and `value` properties. 

```py
computer = Loot("Computer", 2, 12)
print(computer)
# Computer: 
# 	weighs 2,
# 	valued at 12, 
```

We also have a `powerset()` function which creates a list of all combinations.

```py
fruits = ['apple', 'orange', 'grape']
fruit_combinations = power_set(fruits)
print(fruit_combinations)
#[(), ('apple',), ('orange',), ('grape',), ('apple', 'orange'), ('apple', 'grape'), ('orange', 'grape'), ('apple', 'orange', 'grape')]

```

**Note: Codecademy does not endorse thievery!**


Knapsack Without Memoization

Storing answers to sub-problems is an essential aspect of dynamic programming. Let's explore why this is the case.

The <a href="https://en.wikipedia.org/wiki/Fibonacci_number" target="_blank">Fibonacci Sequence</a> is a series of numbers where the next number equals the sum of the previous two, starting with `0` and `1`.

Here's a list of the first 10 Fibonacci numbers: `0, 1, 1, 2, 3, 5, 8, 13, 21`. The zeroth Fibonacci number is 0.

We can express this sequence as a function:

```py
f(n) = f(n - 1) + f(n - 2)
```

We've written a Python function that returns the `n`th Fibonacci number.

Let's add some print statements so we can see how often we're repeating work in the current implementation.

Fibonacci Without Memoization

The Fibonacci sequence is a perfect case to apply dynamic programming. Each Fibonacci number relies on two previous numbers, **and those numbers never change.** We have overlapping sub-problems!

We'll store the answers to sub-problems using _memoization_. Think of it like jotting notes down on a memo.

With each sub-problem, we'll check if we have a note in our memo. If we do, then we can use that information, otherwise, we'll need to do a calculation **and then store that calculation in our memo pad!**

Remember these notes are possible because the answer will always be the same: the `n`th Fibonacci number will never change. Just like the `1 + 1 + 1 + 1` example, we don't need to **recompute** the 3rd and 4th Fibonacci number to calculate the 5th Fibonacci number **if we already know the 3rd and 4th number**.
