Leetcode 322. 零钱兑换 动态规划
原题链接：Leetcode 322. 零钱兑换
class Solution {
public:
int coinChange(vector<int>& coins, int amount) {
if (amount == 0)
return 0;
int n = coins.size();
//dp[i]表示凑成总金额i所需的最少的硬币个数
int dp[amount + 1];
dp[0] = 0;
for (int i = 1; i <= amount; i++) {
dp[i] = INT_MAX;
for (auto x : coins) {
if (i == x)
dp[i] = 1;
else if (i - x > 0 && dp[i - x] != INT_MAX) {
dp[i] = min(dp[i], dp[i - x] + 1);
}
}
}
return dp[amount] == INT_MAX ? -1 : dp[amount];
}
};