322/518-找零钱

LeetCode 322. Coin Change

LeetCode-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:

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

Example 2:

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

method: 完全背包

硬币无穷多，所以是完全背包
dp[j]：装满容量为j的背包的最少硬币数为dp[j]

求最小数，要求最少的硬币个数，递推公式为

dp[j] = min(dp[j], dp[j - coins[i]] + 1)

因为是最少，所以初始化为INT_MAX，并且当需要凑出0元时，只需要0个硬币，所以dp[0]=0

必须满足dp[j - coins[i]] != INT_MAX才能更新当前的背包，不然装不满

int coinChange(vector<int>& coins, int amount) {
    vector<int> dp(amount + 1, INT_MAX);
    dp[0] = 0;
    for (int i = 0; i < coins.size(); i++) {
        for (int j = coins[i]; j <= amount; j++) {
            if (dp[j - coins[i]] != INT_MAX)    // 不然会溢出
                dp[j] = min(dp[j], 1 + dp[j - coins[i]]);
        }
    }
    return dp[amount] == INT_MAX ? -1 : dp[amount];
}

或者用memset初始化为0x3f3f3f3f，就不怕溢出了

static const int N = 1e4 + 5;
int dp[N];
int coinChange(vector<int>& coins, int amount) {
    memset(dp, 0x3f, sizeof(dp));
    dp[0] = 0;
    for (int i = 0; i < coins.size(); i++) {
        for (int j = coins[i]; j <= amount; j++) {
            dp[j] = min(dp[j], dp[j - coins[i]] + 1);
        }
    }
    return dp[amount] == 0x3f3f3f3f ? -1 : dp[amount];
}

---

LeetCode 518. Coin Change 2

LeetCode-518

You are given an integer array coins representing coins of different denominations and an integer amount representing a total amount of money.

Return the number of combinations that make up that amount. If that amount of money cannot be made up by any combination of the coins, return 0.

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

The answer is guaranteed to fit into a signed 32-bit integer.

Example 1:

Input: amount = 5, coins = [1,2,5]
Output: 4
Explanation: there are four ways to make up the amount:
5=5
5=2+2+1
5=2+1+1+1
5=1+1+1+1+1

method

dp[j]：凑成j元有dp[j]种方法

典型的完全背包，要组合数，所以递推方程肯定是累加的形式
dp[j] += dp[j - coins[i]]

求组合数，所以要先遍历物品，再遍历背包
如果是先遍历背包，在遍历物品就变成排列数了

凑成0元有1种方法，就是所有硬币都不用，所以dp[0]=1

int change(int amount, vector<int>& coins) {
    vector<int> dp(amount + 1);
    dp[0] = 1;
    for (int i = 0; i < coins.size(); i++) {
        for (int j = coins[i]; j <= amount; j++) {
            dp[j] += dp[j - coins[i]];
        }
    }
    return dp[amount];
}