Envío 6611

Código

import java.util.HashMap;
import java.util.Scanner;

public class Main {

    public static HashMap<String, Integer> memoization = new HashMap<>();

    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int n = scanner.nextInt();
        int[] coins = new int[n];

        for (int i = 0; i < n; i++) {
            coins[i] = scanner.nextInt();
        }

        int noConsultas = scanner.nextInt();
        int[] consultas = new int[noConsultas];
        for (int i = 0; i < noConsultas; i++) {
            consultas[i] = scanner.nextInt();
        }

        for (int i = 0; i < noConsultas; i++) {
            System.out.println(dpCountCoins(-1, coins, consultas[i]));
        }

    }

    public static int dpCountCoins(int currentCoin, int[] coins, int totalAmount) {
        String key = currentCoin + "-" + totalAmount;
        if (memoization.containsKey(key)) {
            return memoization.get(key);
        }

        if (totalAmount == 0) {
            return 1;
        }

        if (totalAmount < 0) {
            return 0;
        }

        if (currentCoin >= coins.length) {
            return 0;
        }

        int count = 0;

        int coinValue = currentCoin >=0 ? coins[currentCoin] : 0;
        int localAmount = totalAmount - coinValue;
        while (localAmount > 0) {
            for (int i = currentCoin + 1; i <= coins.length; i++) {
                count += dpCountCoins(i, coins, localAmount);
            }
            localAmount = currentCoin >=0 ? localAmount - coinValue : -1;
        }

        if(localAmount == 0){
            count++;
        }

        memoization.put(key, count);
        return count;
    }
}