package leetcode;

/**
 * https://leetcode.com/problems/coin-change/
 */
public class Problem322 {
    public int coinChange(int[] coins, int amount) {
        Integer[] memo = new Integer[amount + 1];
        int result = coinChange(coins, amount, memo);
        if (result == Integer.MAX_VALUE) {
            return -1;
        }
        return result - 1;
    }

    private static int coinChange(int[] coins, int amount, Integer[] memo) {
        if (amount < 0) {
            return Integer.MAX_VALUE;
        } else if (amount == 0) {
            return 1;
        }
        if (memo[amount] != null) {
            return memo[amount];
        }
        int result = Integer.MAX_VALUE;
        for (int coin : coins) {
            int tmp = coinChange(coins, amount - coin, memo);
            if (tmp != Integer.MAX_VALUE) {
                result = Math.min(result, tmp);
            }
        }
        if (result != Integer.MAX_VALUE) {
            result++;
        }
        memo[amount] = result;
        return result;
    }
}

@@ -141,24 +141,650 @@
 t amount) %7B%0A
+        int%5B%5D memo = new int%5Bamount + 1%5D;%0A        for (int i = 1; i %3C= amount; i++) %7B%0A            int min = Integer.MAX_VALUE;%0A            for (int j = 0; j %3C coins.length; j++) %7B%0A                int diff = i - coins%5Bj%5D;%0A                if (diff %3E= 0) %7B%0A                    if (memo%5Bdiff%5D %3E= 0) %7B%0A                        min = Math.min(min, memo%5Bdiff%5D + 1);%0A                    %7D%0A                %7D%0A            %7D%0A            if (min == Integer.MAX_VALUE) %7B%0A                min = -1;%0A            %7D%0A            memo%5Bi%5D = min;%0A        %7D%0A        return memo%5Bamount%5D;%0A    %7D%0A%0A//    public int coinChange(int%5B%5D coins, int amount) %7B%0A//
         Inte
@@ -813,32 +813,34 @@
 er%5Bamount + 1%5D;%0A
+//
         int resu
@@ -869,32 +869,34 @@
  amount, memo);%0A
+//
         if (resu
@@ -914,32 +914,34 @@
 er.MAX_VALUE) %7B%0A
+//
             retu
@@ -943,24 +943,26 @@
  return -1;%0A
+//
         %7D%0A  
@@ -951,32 +951,34 @@
 -1;%0A//        %7D%0A
+//
         return r
@@ -988,23 +988,29 @@
 lt - 1;%0A
+//
     %7D%0A
-%0A
+//%0A//
     priv
@@ -1074,24 +1074,26 @@
 r%5B%5D memo) %7B%0A
+//
         if (
@@ -1102,24 +1102,26 @@
 ount %3C 0) %7B%0A
+//
             
@@ -1138,32 +1138,34 @@
 eger.MAX_VALUE;%0A
+//
         %7D else i
@@ -1178,24 +1178,26 @@
 unt == 0) %7B%0A
+//
             
@@ -1206,16 +1206,18 @@
 turn 1;%0A
+//
         
@@ -1210,32 +1210,34 @@
  1;%0A//        %7D%0A
+//
         if (memo
@@ -1252,24 +1252,26 @@
  != null) %7B%0A
+//
             
@@ -1287,24 +1287,26 @@
 mo%5Bamount%5D;%0A
+//
         %7D%0A  
@@ -1295,32 +1295,34 @@
 t%5D;%0A//        %7D%0A
+//
         int resu
@@ -1337,32 +1337,34 @@
 eger.MAX_VALUE;%0A
+//
         for (int
@@ -1376,24 +1376,26 @@
  : coins) %7B%0A
+//
             
@@ -1444,16 +1444,18 @@
  memo);%0A
+//
         
@@ -1482,32 +1482,34 @@
 er.MAX_VALUE) %7B%0A
+//
                 
@@ -1540,16 +1540,18 @@
 , tmp);%0A
+//
         
@@ -1548,32 +1548,34 @@
 //            %7D%0A
+//
         %7D%0A      
@@ -1560,32 +1560,34 @@
   %7D%0A//        %7D%0A
+//
         if (resu
@@ -1605,32 +1605,34 @@
 er.MAX_VALUE) %7B%0A
+//
             resu
@@ -1637,16 +1637,18 @@
 sult++;%0A
+//
         
@@ -1641,32 +1641,34 @@
 ++;%0A//        %7D%0A
+//
         memo%5Bamo
@@ -1678,24 +1678,26 @@
 %5D = result;%0A
+//
         retu
@@ -1707,16 +1707,18 @@
 result;%0A
+//
     %7D%0A%7D%0A

Update problem 322