Coin Change Problem


Description

LeetCode Problem 322.

You are given an integer array coins representing coins of different denominations and an integer amount representing 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.

Example 1:

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

Example 2:

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

Example 3:

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

Example 4:

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

Example 5:

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

Constraints:

  • 1 <= coins.length <= 12
  • 1 <= coins[i] <= 2^31 - 1
  • 0 <= amount <= 10^4


Sample C++ Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
class Solution {
public:
    int coinChange(vector<int>& coins, int amount) {
        vector<int> dp(amount+1, -1);
        dp[0] = 0;
        if (amount == 0)
            return 0;
        for (int i = 1; i <= amount; i ++) {
            int mincoins = INT_MAX;
            for (int j = 0; j < coins.size(); j ++) {
                if (i - coins[j] >= 0) {
                    if (dp[i-coins[j]] != -1)
                        mincoins = min(mincoins, dp[i-coins[j]] + 1);
                }
            }
            if (mincoins != INT_MAX)
                dp[i] = mincoins;
        }
        return (dp[amount] == 0) ? -1 : dp[amount];
    }
};




Related Posts

Count Numbers With Unique Digits Problem

LeetCode 357. Given an integer n, return the count of...

Combination Sum IV Problem

LeetCode 377. Given an array of distinct integers nums and...

Coin Change Problem

LeetCode 322. You are given an integer array coins representing...

Burst Balloons Problem

LeetCode 312. You are given n balloons, indexed from 0...

Best Time To Buy And Sell Stock With Cooldown Problem

LeetCode 309. You are given an array prices where prices[i]...

Maximum Product Subarray Problem

LeetCode 152. Given an integer array nums, find a contiguous...