import java.util.List;
import java.util.Arrays;
public class Program {
public void printVector(List<Integer> v) {
for (int n : v) {
System.out.print(n + " ");
}
System.out.println();
}
public int totalCombinations(int amount, List<Integer> coins) {
int[] dp = new int[amount + 1];
dp[0] = 1;
for (int coin : coins) {
for (int i = coin; i <= amount; i++) {
dp[i] += dp[i - coin];
}
}
return dp[amount];
}
public static void main(String[] args) {
List<Integer> coins = Arrays.asList(1, 2, 5, 10);
int amount = 6;
// [5,1], [2,2,2], [2,2,1,1], [2,1,1,1,1], [1,1,1,1,1,1]
Program p = new Program();
System.out.println(p.totalCombinations(amount, coins));
List<Integer> coins2 = Arrays.asList(2, 5, 10);
amount = 10;
// [5, 5], [2, 2, 2, 2, 2], [10]
System.out.println(p.totalCombinations(amount, coins2));
}
}
/*
run:
5
3
*/
