package com.fishercoder.solutions;

public class _322 {

    public static class Solution1 {
        /**
         * credit: https://leetcode.com/problems/coin-change-2/discuss/99212/Knapsack-problem-Java-solution-with-thinking-process-O(nm)-Time-and-O(m)-Space
         */
        public int coinChange(int[] coins, int amount) {
            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];
        }
    }

}

@@ -340,17 +340,109 @@
    i
-nt%5B%5D dp =
+f (amount %3C 1) %7B%0A                return 0;%0A            %7D%0A            return coinChange(coins, amount,
  new
@@ -456,13 +456,10 @@
 ount
- + 1
 %5D
+)
 ;%0A  
@@ -468,21 +468,346 @@
     
-    dp%5B0
+%7D%0A%0A        private int coinChange(int%5B%5D coins, int rem, int%5B%5D count) %7B%0A            if (rem %3C 0) %7B%0A                return -1;%0A            %7D%0A            if (rem == 0) %7B%0A                return 0;%0A            %7D%0A            if (count%5Brem - 1
 %5D 
+!
 = 
-1
+0) %7B%0A                return count%5Brem - 1%5D;%0A            %7D%0A            int min = Integer.MAX_VALUE
 ;%0A  
@@ -861,43 +861,97 @@
     
-for (
 int 
-i
+res
  = coin
-; i %3C= amount; i++
+Change(coins, rem - coin, count);%0A                if (res %3E= 0 && res %3C min
 ) %7B%0A
@@ -974,29 +974,21 @@
     
-dp%5Bi%5D += dp%5Bi - coin%5D
+min = 1 + res
 ;%0A  
@@ -1033,24 +1033,96 @@
     
-return dp%5Bamount
+count%5Brem - 1%5D = (min == Integer.MAX_VALUE) ? -1 : min;%0A            return count%5Brem - 1
 %5D;%0A 

update 322