322. Coin Change
https://leetcode.com/problems/coin-change/
You are given coins of different denominations and a total amount of money amount. Write a function to compute 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.
Example 1:
Input: coins =[1, 2, 5], amount =11Output:3Explanation: 11 = 5 + 5 + 1
Example 2:
Input: coins =[2], amount =3Output: -1
Note:
You may assume that you have an infinite number of each kind of coin.
You may assume that you have an infinite number of each kind of coin.
----
Intuition
Initial thoughts
while (target > 0)
pick max coin < target
target = target - max coin
This does not always work
For eg., coins 1, 3, 4 , target = 6
Per above its 3 coins 6 = 4 + 1 + 1
Right answer is two 6 = 3 + 3
So we need to try all combinations
Initial thoughts
while (target > 0)
pick max coin < target
target = target - max coin
This does not always work
For eg., coins 1, 3, 4 , target = 6
Per above its 3 coins 6 = 4 + 1 + 1
Right answer is two 6 = 3 + 3
So we need to try all combinations
Try first coin, then the function reduces to 1 + min (trying other coins)
F(Target) = 1 + min (F(Target - 1st coin))
Some of these recursive calls are repeated
The number of parameters for these recursive function calls is 1
DP with data structure of 1 dimension - array
--
Time - O( T * n)
T - Target Sum
n - number of distinct coins
T - Target Sum
n - number of distinct coins