[leetcode 322] 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.

You may assume that you have an infinite number of each kind of coin.

 

Example 1:

Input: coins = [1,2,5], amount = 11 Output: 3 Explanation: 11 = 5 + 5 + 1

Example 2:

Input: coins = [2], amount = 3 Output: -1

Example 3:

Input: coins = [1], amount = 0 Output: 0

Example 4:

Input: coins = [1], amount = 1 Output: 1

Example 5:

Input: coins = [1], amount = 2 Output: 2

 

Constraints:

• 1 <= coins.length <= 12
• 1 <= coins[i] <= 231 - 1
• 0 <= amount <= 104

 

풀이:

- dp를 사용해서 푸는 문제이다. dp[i]는 i를 만드는데 필요한 동전의 최소 개수

- dp[coins[j]] = 1이 포인트, dp[0] = 0

- dp[i] 는 dp[i-coins[j]] + 1이 된다. 1은 dp[coins[j]]에 해당하는 값

- i와 현재 코인값을 비교하여 현재 코인으로 i를 만들수 있는지 여부를 filter한다

class Solution {
public:
    int coinChange(vector<int>& coins, int amount) {
        int maxCoin = 10000;
        
        int dp[amount+1];
        memset(dp, maxCoin+1, sizeof(dp));
        
        dp[0]=0;
        for(int i=1; i<=amount; i++){
            for(int j=0; j<coins.size(); j++){
                if(i>=coins[j]){
                  dp[i] = min(dp[i], dp[i-coins[j]]+1);
                }
            }
        }
        if(dp[amount] >maxCoin){
            return -1;
        }
        return dp[amount];
    }
};