Dynamic Programming Introduction

Dynamic Programming: INTRODUCTION

In my opinion the best way to learn is through problems and detailed walkthroughs. If you want an article conceptually talking about dynamic programming you can go here. Its TOTALLY fine if you can’t understand it, just having a vague understanding will be helpful.

(Look at my solution and read the article with the code on another tab.) All right so the first problem is minimizing coins. What we want to do is make an array which implements memorization: the ability to efficiently calculate values of a recursive function. We set value[0] = 0 and for each value[x] we check what is the minimum number of coins to get value[x]. We do this by by going through all the values of the coins that are given to us and subtract that value from x. We then use the value[x-weight] to see. Because we start at 0 and continue going up if we reach a number say 6. If we subtract 1, which is one coin, we get 6-1 = 5, and since arr[5] is already updated to be the smallest number of coins possible, we check to see if arr[5] (the minimum amount of coins to get 5) + 1 (the coin we just used to get to arr[3], in this it’s coin 3)  will give you the least number of coins. Then we move on to 5, and then ultimately 7 which repeats the whole process. A little bit intimidating? I would definitely think so. We can do another problem and see if you can get this one.

What we want here is a function: f(x) = number of ways, where x is the desired sum. So let’s follow the given example of 2,3,5. Lets say f(0) = 1, because there’s 1 way to make a sum of 0 and that’s not using any coins and f(1) = 0. Using the same logic as before, every time we want to find a solution for f(x), we should iterate over the coins list and subtract each one for x and add it to f(x). For this problem is should look like f(x) = f(x-2) + f(x-3) + f(x-5). BECAUSE we have array completely updated based on previous calculations, so when you want to find a solution, there are already many solutions to find the answer to the sub-problem. It’s hard to explain so lets go through this one together. So f(2) = f(x-2) = f(0) = 1 (because f(x-3) and f(x-5) are negative). This is correct because if we add the 2 coin to nothing we will get the desired sum of two. In the same vein f(3) = f(1)+f(0) = 1, f(4) = f(1) + f(2) = 1, f(5) = f(0) + f(2) + f(3) = 3. This is because if we add the 5 coin, we have 0 left to add to get the desired sum so there’s 1 way. If we take the 3 coin and subtract it from 5, we have a value of 2 to achieve before we get the desired sum, so we see what f(2) is because we already solved for it, and we see that there’s only one way to get the value of 2 because f(2) = 1. If we take the 2 coin and subtract it from 5 we see that we still have to get a value of 3 to meet the sum of f(5) so we see f(3) = 1. So we add 1+ 1+ 1= 3. Hence we keep on going and eventually we get that f(6) = f(1)+f(3)+f(4) = 2, f(7) = f(2)+f(4)+f(5) = 5, f(8) = f(3) + f(5)+f(6) = 6, and f(9) = f(7) + f(6)+ f(4)= 8, the correct answer. And to keep the value of the functions we create an array called dp[] which basically does all of this but stores f(x) in dp[x]. Check out my solution here.

A problem that I want to leave you off on is if we only counted distinct pairs, instead of {5,4} and {4,5} counting as two pairs we only count them as one. How many of those pairs can you create? The trick is to switch the order of the for loops, look at my solution on github for more information.