322. 零钱兑换

322. 零钱兑换

---

题目链接：322. 零钱兑换

代码如下：

//动态规划，参考：https://leetcode.cn/problems/coin-change/solutions/132979/322-ling-qian-dui-huan-by-leetcode-solution
class Solution {
public:
    int coinChange(vector<int>& coins, int amount) {
        vector<int> dp(amount+1,32767);//存储兑换到amount需要的最少硬币数
        dp[0]=0;

        for(int i=1;i<=amount;i++)
        {
            for(int j=0;j<coins.size();j++)
            {
                if(coins[j]<=i)
                    dp[i]=min(dp[i],dp[i-coins[j]]+1);
            }
        }
        return dp[amount]>amount?-1:dp[amount];
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18