package leetcode;

import java.util.HashMap;
import java.util.Map;

/**
 * https://leetcode.com/problems/coin-change-2/
 */
public class Problem518 {
    public int change(int amount, int[] coins) {
        return coinChange(amount, coins, 0, new HashMap<>());
    }

    private static int coinChange(int amount, int[] coins, int idx, Map<Integer, Integer> memo) {
        if (amount <= 0) {
            if (amount == 0) {
                return 1;
            }
            return 0;
        }
        if (memo.containsKey(amount)) {
            return memo.get(amount);
        }
        int count = 0;
        for (int i = idx; i < coins.length; i++) {
            count += coinChange(amount - coins[i], coins, i, memo);
        }
        memo.put(amount, count);
        return count;
    }

    public static void main(String[] args) {
        Problem518 prob = new Problem518();
        System.out.println(prob.change(5, new int[]{1, 2, 5})); // 4
//        System.out.println(prob.change(3, new int[]{2})); // 0
//        System.out.println(prob.change(10, new int[]{10})); // 1
    }
}
@@ -16,57 +16,8 @@
 e;%0A%0A
-import java.util.HashMap;%0Aimport java.util.Map;%0A%0A
 /**%0A
@@ -139,24 +139,214 @@
 %5B%5D coins) %7B%0A
+        if (amount == 0) %7B%0A            return 1;%0A        %7D%0A        if (coins.length == 0) %7B%0A            return 0;%0A        %7D%0A        Integer%5B%5D%5B%5D memo = new Integer%5Bamount + 1%5D%5Bcoins.length%5D;%0A
         retu
@@ -381,23 +381,12 @@
  0, 
-new HashMap%3C%3E()
+memo
 );%0A 
@@ -463,29 +463,19 @@
 dx, 
-Map%3C
 Integer
-, Integer%3E
+%5B%5D%5B%5D
  mem
@@ -629,28 +629,29 @@
 memo
-.containsKey(amount)
+%5Bamount%5D%5Bidx%5D != null
 ) %7B%0A
@@ -677,20 +677,21 @@
 memo
-.get(
+%5B
 amount
-)
+%5D%5Bidx%5D
 ;%0A  
@@ -866,27 +866,29 @@
 memo
-.put(
+%5B
 amount
-,
+%5D%5Bidx%5D =
  count
-)
 ;%0A  
@@ -1072,18 +1072,16 @@
 ); // 4%0A
-//
         
@@ -1135,18 +1135,16 @@
 ); // 0%0A
-//
         
@@ -1200,15 +1200,81 @@
 ); // 1%0A
+        System.out.println(prob.change(5000, new int%5B%5D%7B1%7D)); // 1%0A
     %7D%0A%7D

Update problem 518