[MUSIC] We are now ready to learn about the key algorithmic technique called dynamic programming, and to learn about the dynamic programming we will look at the very simple change property. You walk to the supermarket, you pay for Compeau and Pevzner book, and you have 40 cents in change. And now cashier is making a decision, how to give you this change? The cashier can give you a quarter, a dime, an extra 5 cents, I think it will be three coins. But cashier also has a choice of giving you 40 pence. The change problem is to find the minimum number of coins to change a given amount of money. And the first thing that come to mind is actually the approach that cashiers all over the world use. They simply look at the amount of money they have to change, and they find the maximum denomination, maximum coin that doesn't exceed the money. They give you this coin, subtract this coin from the amount of money, and iterate. Do we think this approach would produce an optimal solution? In fact, it will produce an optimal solution in United States, but not in Tanzania. Tanzania has beautiful coin, shown here, and they actually, in addition to quarters, they have a 20 cents coin. So, while great algorithm, in Tanzania, will result in three coins as a change, because it starts from 25 as largest coin, smaller than 40, then it's ten, then it's five. The right thing to change money in Tanzania is simply to give you two 20 cents coin. So what algorithm should we design to change money in Tanzania optimally? Let's design a recursive change algorithm. And let's imagine that we are in a strange country where there are only three coins: 6, 5 and 1 cents. How would we change 9 cents using these coins. Well to change 9 cents, to find optimal amount of money (coins) optimal means number of coins to change 9 cents, we can find minimum number of coins to change 8 cents and to add 1 penny. Or minimum number of coins to change 4 cents and to add 5 cents coin one more coin, or to find the minimum number of coins to change 3 cents and add more coin, right. And therefore the minimum number of coins for 9 cents is the minimum of the minimum number of coins for 8, 4 or 3 cents plus one (coin) Makes sense? Okay. but, to find the minimum number of coins for 3, 4 and 8 cents, we once again need to find the minimum number of coins for other values of money, and we will be doing this recursively. So, the general formula for whatever number of coins we may have for denomination will be the minimum number of coins for the amount of money equal to the minimum of the following d expressions. Where d is the number of coins in the currency. It is the minimum number of coins for money minus coin one, minus coin two... And finally minimum number of coins for money minus coin d. Plus one for all these values. And there is a simple recursive change algorithm that implements this approach. So every time we need to change the amount of coins equal to money, we have d recursive calls. And compute the minimum number of change for money minus coin i. Do you think this is a good algorithm? This algorithm is definitely correct, but it will take quite enormous time to solve the problem. Let's see how it works. Let's start from 76 cents and see how our algorithm works. To compute the change for 76 cents, we need to compute first the change for 70 cents, 71 cents, and 75 cents And we continue this way recursively, and we see that to compute (the answer for) 76 cents, we actually need to compute the optimal amount of change for 69 cents twice. But if we go further, we see that we actually need to compute it more than twice. Now we see that we need to compute it five (more) times. In reality, we actually need to compute the optimal coin combination for 69 cents six times. Okay, but how many times do we need to compute optimal combination for 30 cents? It turns out that we need to compute it trillions of times, which means that our algorithm is correct, but it will (practically) never end. Because it takes so much time. We need to come up with a different approach. Instead of changing money greedily, let's try something different. Wouldn't it be wonderful to compute all the values minimum number of coins for money minus coin i. That all values that we need to compute minimum number of coins for the amount of money. If we pre-computed all those values, then computed minimum number of coins for a given amount of money would be a simple exercise, and a very fast exercise, right? And to implement it the only thing that we need, instead of the time-consuming calls lead to recursive change for money minus coin i, we simply look up the values of the minimum number of coins for money minus coin. So how our algorithm changes? We'll, instead of moving from larger values to smaller values to fill this table, we will now move from smaller values to larger values. For example, what is the minimum number of coins to change zero cents? Of course it is zero. What is the minimum number of coin to change one cent? Of course it is one. Two? It is two. Three? It is three. And four, it is four. And now we come to changing five coins. And they can be changed in two different ways. They can be changed either by taking minimum number of coins to change zero, and adding one coin. Or minimum number of coins to change four, and adding one coin. Which of these numbers is smaller? This is a simple check, and we choose to change five coin by adding a 5 cents coin to the existing combination. Now, we are facing a problem of changing 6 cents. In this case there are three choices. We can either use optimal change for 5 cents or 1 cent or 0 cents. And depending which of them is the smallest, will decide how to change 6 cents. So in this case It turns out that the best strategy is simply to add 6 cent coin to the combination. We continue further and further until we arrive to changing nine coins. Of course, it is a much faster algorithm and we can implement it differently without any recursive calls. Simply, at every stage to compute the amount of coins (for a concrete money), we need to look at d previously computed values where d is the number of denominations. That's all. That's the idea developed by Richard Bellman called dynamic programming, which is arguably the most popular algorithmic technique today. Amazingly, 60 years ago, when Richard Bellman was developing this technique, it was absolutely unclear that this technique has any practical applications. In fact, Richard Bellman was working on a project for Air Force, and it turned out, some students sometimes ask you where is the programming in the dynamic programming? It turns out there is no programming in dynamic programming because at that time, his approach seemed completely impractical. And he worked for the Air Force, so he wanted to hide that he was really doing mathematics from the secretary of defense. He was a prominent mathematician by this time. This is a quote from Richard Bellman. What name could I choose? I was interested in planning, but planning is not a good word for various reasons. I decided, therefore, to use the word programming. And I wanted to get across the idea that this was dynamic. It was something not even a congressman could object to, so I use it as an umbrella for my activities. Amazingly enough, the most popular algorithmic technique today was invented as an umbrella for a mathematical activity while working on the Air Force project.