aboutsummaryrefslogtreecommitdiff
path: root/coin_change2.c
blob: 086ba0c11ca018de32e9d9d13d62f38334dfeccb (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
32
33
// 518. Coin Change II
#include <stdio.h>
#include <stdlib.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.
 */

int change(int amount, int *coins, int coins_size) {
  if (!coins_size) {
    if (!amount)
      return 1;
    return 0;
  }
  int *dp = (int *)calloc(amount + 1, sizeof(int));
  dp[0] = 1;
  for (int i = 0; i < coins_size; i++)
    for (int j = coins[i]; j < amount + 1; j++)
      dp[j] += dp[j - coins[i]];
  return dp[amount];
}

int main() {
  int c1[] = {1, 2, 5}, c2[] = {2}, c3[] = {10};
  printf("%d\n", change(5, c1, 3));  // expect: 4
  printf("%d\n", change(3, c2, 1));  // expect: 0
  printf("%d\n", change(10, c3, 1)); // expect: 1
}