零钱兑换

Problem

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

Constraints:

• 1 <= coins.length <= 12
• 1 <= coins[i] <= \(2^{31} - 1\)
• 0 <= amount <= \(10^4\)

Idea

Use bottom-up dynamic programming over the amounts, like an unbounded knapsack. Let dp[x] be the fewest coins needed to make amount \(x\), with dp[0] = 0.

To make \(x\), the last coin can be any coin \(c \le x\), so dp[x] = min(dp[x - c] + 1) over all such coins. Fill dp from 1 up to amount. Start every entry at amount + 1, which works as infinity because no answer needs more than amount coins. If dp[amount] is still amount + 1 at the end, return -1.

Time complexity: \(O(n \cdot A)\), Space complexity: \(O(A)\), where \(n\) is the number of coins and \(A\) is the amount

Pseudo Code

dp = array of size amount + 1, filled with amount + 1;   // amount + 1 means unreachable
dp[0] = 0;
for (x = 1; x <= amount; x++) {
    for (c in coins) {
        if (c <= x) {
            dp[x] = min(dp[x], dp[x - c] + 1);
        }
    }
}
if (dp[amount] > amount) {
    return -1;
}
return dp[amount];