aboutsummaryrefslogtreecommitdiff
path: root/coin_change2.cpp
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
}