blob: 4680c956c37b6a451accbe7cd264df315960abd6 (
plain)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
|
// 518. Coin Change II
#include "leetcode.h"
/*
* given an integer array 'coins' representing cons of different denominations
* and an integer 'amount' representing a total amount of money. return the
* number of combinations that make up the amount. if that amount of money
* cannot be made up by any combination the coins, return 0. you may assume that
* you have an infinite number of each kind of coin. the answer is guaranteed to
* fit into a signed 32-bit integer.
*/
class Solution {
public:
int change(int amount, vector<int> &coins) {
vector<int> dp(amount + 1, 0);
dp[0] = 1;
for (int i : coins)
for (int j = i; j <= amount; j++)
dp[j] += dp[j - i];
return dp[amount];
}
};
int main() {
Solution obj;
vector<int> c1 = {1, 2, 5}, c2 = {2}, c3 = {10};
printf("%d\n", obj.change(5, c1)); // expect: 4
printf("%d\n", obj.change(3, c2)); // expect: 0
printf("%d\n", obj.change(10, c3)); // expect: 1
}
|