Coin Change II

Medium Dynamic Programming

Count the number of distinct ways to make an amount using unlimited coins of the given denominations.

Sample input

amount = 5, coins = [1, 2, 5]

Sample output

Solution

def change(amount, coins):
    dp = [0] * (amount + 1)
    dp[0] = 1
    for coin in coins:
        for x in range(coin, amount + 1):
            dp[x] += dp[x - coin]
    return dp[amount]

print(change(5, [1, 2, 5]))

function change(amount, coins) {
  const dp = new Array(amount + 1).fill(0);
  dp[0] = 1;
  for (const coin of coins) {
    for (let x = coin; x <= amount; x++) {
      dp[x] += dp[x - coin];
    }
  }
  return dp[amount];
}

console.log(change(5, [1, 2, 5]));

public class Main {
    static int change(int amount, int[] coins) {
        int[] dp = new int[amount + 1];
        dp[0] = 1;
        for (int coin : coins) {
            for (int x = coin; x <= amount; x++) {
                dp[x] += dp[x - coin];
            }
        }
        return dp[amount];
    }

    public static void main(String[] args) {
        System.out.println(change(5, new int[]{1, 2, 5}));
    }
}

fun change(amount: Int, coins: IntArray): Int {
    val dp = IntArray(amount + 1)
    dp[0] = 1
    for (coin in coins) {
        for (x in coin..amount) {
            dp[x] += dp[x - coin]
        }
    }
    return dp[amount]
}

fun main() {
    println(change(5, intArrayOf(1, 2, 5)))
}

func change(_ amount: Int, _ coins: [Int]) -> Int {
    var dp = [Int](repeating: 0, count: amount + 1)
    dp[0] = 1
    for coin in coins where coin <= amount {
        for x in coin...amount {
            dp[x] += dp[x - coin]
        }
    }
    return dp[amount]
}

print(change(5, [1, 2, 5]))

int change(int amount, List<int> coins) {
  final dp = List.filled(amount + 1, 0);
  dp[0] = 1;
  for (final coin in coins) {
    for (var x = coin; x <= amount; x++) {
      dp[x] += dp[x - coin];
    }
  }
  return dp[amount];
}

void main() {
  print(change(5, [1, 2, 5]));
}

#include <iostream>
#include <vector>
using namespace std;

int change(int amount, const vector<int>& coins) {
    vector<int> dp(amount + 1, 0);
    dp[0] = 1;
    for (int coin : coins) {
        for (int x = coin; x <= amount; x++) {
            dp[x] += dp[x - coin];
        }
    }
    return dp[amount];
}

int main() {
    cout << change(5, {1, 2, 5}) << endl;
    return 0;
}

#include <stdio.h>

int change(int amount, int *coins, int numCoins) {
    int dp[100] = {0};
    dp[0] = 1;
    for (int c = 0; c < numCoins; c++) {
        for (int x = coins[c]; x <= amount; x++) {
            dp[x] += dp[x - coins[c]];
        }
    }
    return dp[amount];
}

int main() {
    int coins[] = {1, 2, 5};
    printf("%d\n", change(5, coins, 3));
    return 0;
}