Leetcode322. 零钱兑换【动态规划】-蒲公英云

Leetcode322. 零钱兑换【动态规划】

难度：中等
题目描述：

给你一个整数数组 coins ，表示不同面额的硬币；以及一个整数 amount ，表示总金额。
计算并返回可以凑成总金额所需的最少的硬币个数。如果没有任何一种硬币组合能组成总金额，返回 -1 。
你可以认为每种硬币的数量是无限的。

示例 1：

输入：

coins = [1, 2, 5], amount = 11

输出：

3

解释：

11 = 5 + 5 + 1

示例 2：

输入：

coins = [2], amount = 3

输出：

-1

示例 3：

输入：

coins = [1], amount = 0

输出：

0

示例 4：

输入：

coins = [1], amount = 1

输出：

1

示例 5：

输入：

coins = [1], amount = 2

输出：

2

提示：

1 <= coins.length <= 12
1 <= coins[i] <= 231 - 1
0 <= amount <= 104

class Solution { 
public:
    int ans = 0;
    int coinChange(vector<int>& coins, int amount) { 
        if(amount<1){ 
            return 0;
        }
        // 初始化相应金额的dp数组
        vector<int> dp(amount+1, amount+1);
        dp[0]=0;
        for(int j=1;j<amount+1;j++){ 
            for(int i=0;i<coins.size();i++){ 
                if(coins[i]<=j){ 
                    dp[j]=min(dp[j-coins[i]]+1,dp[j]);
                }
            }
        }
        if(dp[amount]>amount){ 
            return -1;
        }else{ 
            return dp[amount];
        }
    }
};