322

322. Coin Change (Medium)

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:

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

Companies:
Amazon, Microsoft, Walmart Labs, Bloomberg, Goldman Sachs, Apple, Google, Uber, Facebook, Adobe, Airbnb

Related Topics:
Dynamic Programming

Similar Questions:

• Minimum Cost For Tickets (Medium)

Solution 1. DP

Let dp[i + 1][t] be the minimum coins needed to get a total amount of money t with the first i + 1 coins.

dp[i + 1][t] = min(
                dp[i][t],                    // don't use A[i]
                dp[i][t - A[i]] + 1,         // use A[i] once
                dp[i][t - A[i] * 2] + 2,     // use A[i] twice
                ...
            )
dp[i + 1][t] = min(dp[i][t], 1 + dp[i + 1][t - A[i]]) where 0 <= i < N
dp[i][0] = 0 where 0 <= i <= N

// OJ: https://leetcode.com/problems/coin-change/
// Author: github.com/lzl124631x
// Time: O(NT)
// Space: O(NT)
class Solution {
public:
    int coinChange(vector<int>& A, int T) {
        sort(begin(A), end(A), greater<>());
        int N = A.size(), INF = 0x3f3f3f3f, dp[13][10001] = {};
        memset(dp, 0x3f, sizeof(dp));
        for (int i = 0; i <= N; ++i) dp[i][0] = 0;
        for (int i = 0; i < N; ++i) {
            for (int t = 1; t <= T; ++t) {
                dp[i + 1][t] = min(dp[i][t], t - A[i] >= 0 ? 1 + dp[i + 1][t - A[i]] : INF);
            }
        }
        return dp[N][T] == INF ? -1 : dp[N][T];
    }
};

Or use 1D array instead.

// OJ: https://leetcode.com/problems/coin-change/
// Author: github.com/lzl124631x
// Time: O(NT)
// Space: O(T)
class Solution {
public:
    int coinChange(vector<int>& A, int T) {
        sort(begin(A), end(A), greater<>());
        int N = A.size(), INF = 0x3f3f3f3f, dp[10001] = {}, next[10001] = {};
        memset(dp, 0x3f, sizeof(dp));
        dp[0] = 0;
        for (int i = 0; i < N; ++i) {
            memset(next, 0x3f, sizeof(next));
            next[0] = 0;
            for (int t = 1; t <= T; ++t) {
                next[t] = min(dp[t], t - A[i] >= 0 ? 1 + next[t - A[i]] : INF);
            }
            swap(next, dp);
        }
        return dp[T] == INF ? -1 : dp[T];
    }
};

Solution 2. DP

If we switch the order of t and i, we can use 1D array directly.

Let dp[t][i + 1] be the minimum coins needed to get a total amount of money t with the first i + 1 coins.

dp[t][i + 1] = min(
                    dp[t][i],                  // don't use A[i]
                    dp[t - A[i]][i] + 1,       // use A[i] once
                    dp[t - A[i] * 2][i] + 2,   // use A[i] twice
                    ...
                )
dp[t][i + 1] = min(dp[t][i], 1 + dp[t - A[i]][i])   where 0 <= i < N
dp[0][i] = 0 where 0 <= i <= N

Let dp[t] be the minimum coins needed to get a total amount of money t with all coins.

dp[t] = dp[t - C] + 1 where C is the last coin's denomination
dp[t] = min( dp[t - A[i]] + 1 | 0 <= i < N && t - A[i] >= 0 )
dp[0] = 0

// OJ: https://leetcode.com/problems/coin-change/
// Author: github.com/lzl124631x
// Time: O(NT)
// Space: O(T)
class Solution {
public:
    int coinChange(vector<int>& A, int T) {
        int N = A.size(), INF = 0x3f3f3f3f, dp[10001] = {};
        memset(dp, 0x3f, sizeof(dp));
        dp[0] = 0;
        for (int t = 1; t <= T; ++t) {
            for (int i = 0; i < N; ++i) {
                dp[t] = min(dp[t], t - A[i] >= 0 ? 1 + dp[t - A[i]] : INF);
            }
        }
        return dp[T] == INF ? -1 : dp[T];
    }
};