Dynamic Programming… is not as complicated as you thought! (LeetCode 322. Coin Change)
Before getting started……
About two months ago, I wrote another blog about the fundamental concepts of Dynamic Programming, and I said I’ll write more DS&A solutions for it. Although this article is a bit overdue, I am hoping for those who have been patiently waiting for those solutions.
I’ll wrap up the previous blog, with the Coin Change Problem!
Important: if you’ve finished reading my previous blog on LinkedIn and you don’t want to reread it, you could just jump to the paragraph “DP Characteristics, with LeetCode 322. Coin Change”!
Dynamic Programming, aka DP, is always something people talk about when preparing for DS&A interviews, or doing their LeetCode march. When I was in the a/A Bootcamp, I discussed this with some instructors and found that DP is so hot a topic because:
- It solves many optimization problems — not only in the CS field. For example, these days, my bosom bestie researching Space Engineering suddenly asked me how to do dynamic programming.
- It frequently gives better performance, which means smaller time complexity. (But not always, so don’t regard DP as a master key!)
- The most important point: IT IS HARD TO UNDERSTAND!
(Thank you, Clement Mihailescu, for sharing this Easter Egg!)
I don’t know whether there’s somebody not trapped by DP at first glance — maybe Terence Tao could be the one. But personally, DP was acing me for a long time before I started acing it. One key point was when I saw this paragraph on the wiki page of DP:
What title, what name, could I choose? In the first place I was interested in planning, in decision making, in thinking. But planning, is not a good word for various reasons. I decided therefore to use the word “programming”. I wanted to get across the idea that this was dynamic, this was multistage, this was time-varying. … Thus, I thought dynamic programming was a good name. It was something not even a Congressman could object to. So I used it as an umbrella for my activities.
According to R. Bellman, who brought DP to our world, the name was to some extent “fabricated” since other names like “decision research” would not make a gentleman from the military feel comfortable. So, one thing we could clarify here is, the “Programming” in DP doesn’t mean the action that we’re sitting beside a laptop, typing lines of code and bugs… It is “Programming” in the mathematical aspect, which means “Decision-Making.”
Decision-Making ?!
Yes, but not that simple. With the word “Dynamic”, we’ll know that “Decision-Making” is not as simple as “directly coming up with something” that happens in our brain 35,000 times every day; on the contrary, the “Decision” is “Made” in a “Multistaged” way.
I’ll always suggest this explanation for DP, which is the top answer to this Quora question:
How should I explain dynamic programming to a 4-year-old?
Imagine one thing: Jerry is trying to give Morty $0.32. Of course, it is usually for Jerry one coin with the denomination of $0.32 (rant: I’m afraid that’s something Jerry might try…). So he has to think how to pile up changes for this value — A quarter, a Nickel, and two Cents, or, three Dimes and two cents.
Good job! Now he knows how to give Morty $0.32. How about 0.33$?
Even Jerry could get the solution quickly — just add another cent to the previous solution(s)!
That’s it. That’s how it works. We know that 0.33$ is just one cent more than $0.32, and the plan of piling up $0.32 was already made. We’ve had a solution for a complex problem, and now we’re solving another problem, which might be just one step/number/coin further than the previous one. We’ll definitely reference the solution of the previous one, because it is a“predecessor stage” of our current problem.
Feel better with DP now? Cool, let’s start with some concepts, with a LeetCode challenge!
DP Characteristics, with LeetCode 322. Coin Change
Now, we’ll introduce LeetCode 322. Coin Change, which is a classic DP problem:
You are given an integer array
coinsrepresenting coins of different denominations and an integeramountrepresenting a total amount of money.Return the fewest number of coins that you need to make up that amount. If that amount of money cannot be made up by any combination of the coins, return
-1.You may assume that you have an infinite number of each kind of coin.
In short: we want to know the fewest number of coins, with a given coin selection, when we want to get a specific amount.
Here are some examples:
Example 1
Input: coins = [1,2,5], amount = 11
Output: 3
Explanation: 11 = 5 + 5 + 1Since we have coins denominated at 1, 2, and 5, for an amount of 11, 5+5+1 will be the changing method resulting in the fewest coins. We could, of course, quickly come up with other solutions, like 2 + 2 + 2 + 2 + 2 + 1 or 11 * 1, but none of them could make the number 3.
Example 2
Input: coins = [2], amount = 3
Output: -1In this case, we only have coins denominated at 2, but the total amount is 3. So we could quickly know that this amount is impossible for such coins (unless half of a coin is a legal tender in this society… but now it’s not), so the output should be -1 since it means “impossible”.
Example 3
Input: coins = [1], amount = 0
Output: 0This is also easy to understand. When the expected amount is 0, no matter what kind of coins we have, the fewest number will be 0.
Using DP Characteristics to Analyze a DP Problem
Now we have a problem. Since we’re talking about DP, we’ll try DP on it. However, the first question is always:
Is it possible to solve this problem with DP?
That’s a crucial question, since we cannot always introduce DP into one problem. So what kind of problems will give us a chance to use DP?
The answer is two critical characteristics of DP: DP State, and DP Transition Equation.
DP State
Mostly we’ll say DP State is the solution for a “smaller problem” or “sub-problem”, which generally means the solution for a smaller number/structure than the input. For most problems, it will be the optimized solution for a “smaller one”. You could also say the answer we finally want is also a state, since it could also be used for a bigger input, but now we are focusing on how to get the answer we are looking for.
So defining the “state” is the first and most crucial step for DP problems, since we could not DP it without this definition. For this problem, we could think about one thing: “what” of a smaller amount helps solve the final amount?
You might come up with a lot of things, but let’s look at the expected output of this problem: it is the minimal number of coins required to reach the amount “n”— let’s call it num_change(n). So, why don’t we try to make this our state?
Yes, it looks so good, since if we know we need at least one coin to get the denomination of 5, which is num_change(5) = 1, then we know we need two coins to have the amount of 6: num_change(6) = num_change(5) + 1 (since there’s a coin valued 1), based on the solution with “5”. Also, when we are calculating 7, it will be the same logic, similar to the example between Jerry & Morty…
Wait! As I mentioned, it is a try, because we still have to do some checks before making sure “the minimal number of coins to achieve a specific amount” is the state. What we are going to check is the two vital features of the state:
1. Optimized Sub-Solution
As we mentioned above, one state will be the optimized solution for a sub-problem — with this logic, we could say each state is an optimized sub-solution.
Let’s think about our state definition with an amount— num_change(10) means the number of coins to reach the amount of 10. We know that two coins is the best choice here, but, are there any other combinations? Of course yes. For example, we could make it 5 + 2 + 2 + 1 with 4 coins, or 5 + 2 + 1 + 1 + 1 with 5 coins…
However, what’s the definition of “optimized” in this problem? Based on the description, we know it’s the “minimal” number of coins. So do we have an optimized sub-solution for the sub-problem with an amount of 10? Of course, it is 2 — since we have coins with the denomination of 5. So we could say num_change(10) = 2, which means the optimized sub-solution for the sub-problem is 2 (a 5-denominated-coin). Remember, we have to record it somewhere in the code; otherwise, the following state won’t find it!
2. No After-Effect from how we Solve it
The calculation process of one state and its earlier states, has no after-effect, on the late states. You might see many articles suggesting this point of DP (in many languages). Other words for this point might be, “The future is not related to the process of the past”. In DP problems, when we reach a state, all of its earlier states won’t be changed. Also, we’ll only use the solution of the earlier recorded state(s), but we don’t have to care how we got the solution previously.
Let’s continue with the example num_change(10). Now we know that num_change(10) = 2, and we look forward to knowing the answer to num_change(11).
Can we calculate this answer based on num_change(10)? — Yes.
When we are calculating num_change(11), would num_change(10) got influenced? — No.
Do we need to know how we calculated num_change(10) when solving num_change(11)? — No, we only want to refer to its result: num_change(10) = 2.
So that’s the meaning of “No after-effect” — we only want to utilize the previous states(solutions), and using it won’t change its value.
State Transition Logic(Equation)
Actually, we’ve already finished doing some state transition, because it means “getting one state based on the earlier state(s)”. When we were calculating num_change(11), we were referring the recorded num_change(10), so there is a transition logic exposed:
num_change(11) = num_change(10) + 1 because we have 1-denominated coins.
So, we could guess for num_change(n), we would have such a equation:
num_change(n) = num_change(n-1) + 1 because we have 1-denomination coins…
Looks strange? Yes, excellent intuition! Don’t forget that we have other coins and are always looking forward to the optimized solution and sub-solutions!
Let’s check our intuition. Imagine we finished calculating num_change(14) = 4 (5 + 5 + 2 + 2), and based on the DP logic, we’ve finished calculating all the other sub-solutions before 14 (num_change(1) to num_change(13)). Now we want to get num_change(15).
What will happen if we directly follow this logic:
num_change(n) = num_change(n-1) + 1?
We’ll get num_change(15) = num_change(14) + 1 = 4 + 1 = 5… but with a human brain that is good at fuzzy fast reaction, we’ll suddenly deny it: “No! It should be 3! Three 5-denominated coins!”
Cool! We found that we made a mistake, and now we can learn from it — since my company Strategio is suggesting this!
Let’s try to trace back. Why did we make this mistake?
The answer is clear — the previous logic was only considering the scenario of adding a 1-denominated coin. However, we still have coins with denominations of 2 and 5.
Thus, the mistake is: num_change(15) may not only transferred by num_change(14), but also num_change(13) or num_change(10). This reveals one important thing about state transition logic: there might be more than one potential transition for obtaining a state, so we must check each to ensure we can find the optimized answer.
So there will be three potential transitions based on our coin box:
- num_change(14) + 1 with a 1-coin => 4 + 1 => 5 (5+5+2+2+1)
- num_change(13) + 1 with a 2-coin => 4 + 1 => 5 (5+5+2+1+2)
- num_change(10) + 1 with a 5-coin => 2 + 1 => 3 (5+5+5)
(Don’t forget when we are calculating num_change(15), we should have already calculated and recorded the result of num_change(14), num_change(13), and num_change(10)!)
As mentioned above, the optimized answer should be the one with the least coins, so it’s min(5,5,3), which is 3. Now we’ve got the correct answer: num_change(15) = 3!
Wrap Up
So let’s wrap up the logic of solving the Coin Change problem:
- Find out the state with two features: “optimized sub-solution” and “no after-effect” — num_change(n) = the minimal number required for achieving an amount of n.
- Find out the state transition logic: num_change(n-c) = num_change(n), where c is one kind of coin.
- Compare all the transitions which could lead us to num_change(n-c); in other words, check every possible c.
- Finally, we could find the optimized one with the smallest coin number!
Coding time!
Now let’s turn our thinking into code!
The function itself is defined like this:
public int coinChange(int[] coins, int amount){
//TODO: edge cases
//TODO: initialization
//TODO: calculating all states
//TODO: return
}As the problem description mentioned, we have given coins of different denominations and a desired amount.
First, we must think about an edge case. It is actually indicated by example 3, which means if it’s asking for the amount of 0, then the number of coins would be 0 too. 0 for 0, it’s fair.
public int coinChange(int[] coins, int amount){
if(amount==0)return 0; // edge case: if the amount is 0
//TODO: initialization
//TODO: calculating all states
//TODO: return
}Then we’ll initialize our num_change states, which will be an array here, since it gives us an O(1) query for every calculated and recorded state. Also, at the very beginning, we’ll fill it with amount+1 coins, because it is an impossible solution (since no one will give me three coins for 2 cents). So, after all the checks, if num_change(amount) is still amount+1, it means that we cannot find a solution. According to the description, we’ll return -1 at this point:
public int coinChange(int[] coins, int amount){
if(amount==0)return 0;// edge case: if the amount is 0
int maxNum = amount + 1; // an impossible value for the solution
int[] num_change = new int[maxNum]; // fixed-length of the array for maxNum States
Arrays.fill(num_change, maxNum);// fill them with the impossible number
num_change[0] = 0;
//TODO: calculating all states
if(num_change[amount] == maxNum)num_change[amount] = -1;
return num_change[amount];
}
And now, we’ll write the loop with the logic we’ve discussed: from the earliest state to the final solution, which means we calculate from num_change(1) to num_change(amount)!
And in each iteration, we have to check each potential transition so we can finally choose the optimized result for sub-solutions and the final solution. Also, when we are calculating n, checking a coin with a denomination c, and we have n — c < 0 — it means that we could not use this coin to achieve such an amount, since you’ll never pay me 5 cents with any quarters:
public int coinChange(int[] coins, int amount){
if(amount==0)return 0;// edge case: if the amount is 0
int maxNum = amount + 1; // an impossible value for the solution
int[] num_change = new int[maxNum]; // fixed-length of the array for maxNum States
Arrays.fill(num_change, maxNum);// fill them with the impossible number
num_change[0] = 0;// 0 means 0
for(int i = 1; i <= amount; i ++){// from state 1 to final amount
for(int coin: coins){// check each coin, means each potential transition
// if the coin denomination is smaller than i
// and the potential sub-solution won't reach the possible maximum number
if(i - coin >= 0 && num_change[i - coin] <= amount){
//the minimal value between current one and previously recorded one
num_change[i] = Math.min(num_change[i], num_change[i-coin]+1);
}
}
}
if(num_change[amount] == maxNum)num_change[amount] = -1;// no possible solution!
return num_change[amount];// return the result
}You could run it on your own LeetCode and see whether it works now!
Afterwords
Explaining DP is really challenging work, especially since I’m avoiding too many mathematical concepts and formulae. I hope this article will make you feel better about DP problems, and open you a way to ace them.
Feel free to leave any comments & constructive suggestions!
