package DynamicProgramming;
import java.util.Arrays;
import java.util.Collections;
import java.util.Comparator;
import java.util.HashMap;
import java.util.List;
import java.util.Scanner;

public class CoinChange2{
    public static void main(String[] args) throws Exception { 
       int amount = 12;
    int[] coins = {2, 4, 5};

      System.out.print(change(amount, coins));
      
    }
   // Two key points:
// create memoization with respect to 0 (thus initialize memo with null)
// in a recursive call using index i without increment
// Last key respects cases 1 + 2 == 2 + 1 and should be counted as one way of amount decompositions.

    public static int change(int amount, int[] coins) {

        return change(amount, coins, 0, new Integer[amount + 1][coins.length]);

    }
    
    public static int change(int amount, int[] coins, int pos, Integer[][] memo) {
        if (amount == 0) return 1;
        if (amount < 0) return 0;

        if (memo[amount][pos] != null) return memo[amount][pos]; // first key

        int ret = 0;

        for (int i = pos; i < coins.length; i++) {
            ret += change(amount - coins[i], coins, i, memo); // second key - "i" without increment
        }

        memo[amount][pos] = ret;
        return ret;
    }

}