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

题目链接：https://leetcode.com/problems/coin-change/

【DP、BFS】322. Coin Change - 简书

01-背包、完全背包、多重背包及其相关应用 - 简书

思路：这题使用完全背包的想法，不限制物品的数量，可以重复的拿，所以内层循环从小到大遍历，这里就是用min来更新。

dp[i]:代表组成金额是i需要的硬币数量，初始值设置成inf，只有dp[0]=0.

class Solution {
public:
    int coinChange(vector<int>& coins, int amount) {
        int dp[amount+1],inf=0x3f3f3f3f;
        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-coins[i]]+1,dp[j]);
            }
        }
        if(dp[amount]==inf)
        {
            cout<<dp[amount]<<endl;
            return -1;
        }
        else
        {
            return dp[amount];
        }
    }
};

class Solution {
    /**
    2024年8月29日21:38:47
    dp[i]:组成面额是i的最少硬币个数
    状态转移方程
    dp[i]=Math.min(dp[i-coins[j]]+1,dp[i])
    coins[j]是遍历所有的硬币面额
     */
    public int coinChange(int[] coins, int amount) {
        int[] dp=new int[amount+1];
        int len=coins.length;
        int N=amount+1;
        for(int i=0;i<=amount;i++){
            // 默认是N表示不可能组成的次数
            dp[i]=N;
        }
        dp[0]=0;
        for(int i=1;i<=amount;i++){
            for(int j=0;j<len;j++){
                // 金额可能很大，超出amount了，所以要判断下
                if(i>=coins[j]){
                    dp[i]=Math.min(dp[i-coins[j]]+1,dp[i]);
                } 
            }
        }
        return dp[amount]==N?-1:dp[amount];
    }
}