diff options
Diffstat (limited to 'other/coin_change2.cpp')
-rw-r--r-- | other/coin_change2.cpp | 31 |
1 files changed, 31 insertions, 0 deletions
diff --git a/other/coin_change2.cpp b/other/coin_change2.cpp new file mode 100644 index 0000000..4680c95 --- /dev/null +++ b/other/coin_change2.cpp @@ -0,0 +1,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 +} |