Description
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.
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
Note
You may assume that you have
an infinite
number of each kind
of coin.
Solution 1(C++)
class Solution{
public:
int coinChange(
vector<int>& coins,
int amount){
vector<int> dp(amount+
1, amount+
1);
dp[
0] =
0;
for(
int i=
1; i<amount+
1; i++){
for(
int j=
0; j<coins.size(); j++){
if(coins[j] <= i){
dp[i] = min(dp[i], dp[i-coins[j]]+
1);
}
}
}
retrun dp[amount] > amount ? -
1 : dp[amount];
}
};
后续更新
其他类似的题目可以参考：
LeetCode-416. Partition Equal Subset SumLeetCode-494. Target SumLeetCode-279. Perfect SquaresLeetCode-139. Word Break
算法分析
这道题与：LeetCode-139. Word Break 类似，但是与：LeetCode-279. Perfect Squares 非常类似了。就不多啰嗦了。
程序分析
略。
