package com.fishercoder.solutions;

import java.util.Arrays;

public class _322 {

    public static class Solution1 {
        public int coinChange(int[] coins, int amount) {
            if (amount < 1) {
                return 0;
            }
            int[] count = new int[amount];
            int result = helper(coins, amount, count);
            return result;
        }

        //remaining means the remaining coins after the last step;
        //count[remaining] means the minimum number of coins to sum up to remaining
        private int helper(int[] coins, int remaining, int[] count) {
            if (remaining < 0) {
                return -1;//not valid case, thus, per problem description, we should return -1
            }
            if (remaining == 0) {
                return 0;//completed, this is also a base case for this recursive function
            }
            if (count[remaining - 1] != 0) {
                return count[remaining - 1];//already computed, so reuse it.
            }
            int min = Integer.MAX_VALUE;
            for (int coin : coins) {
                int res = helper(coins, remaining - coin, count);
                if (res >= 0 && res < min) {
                    min = 1 + res;
                }
            }
            return count[remaining - 1] = (min == Integer.MAX_VALUE) ? -1 : min;
        }
    }

    public static class Solution2 {
        //dp solution
        public int coinChange(int[] coins, int amount) {
            int max = amount + 1;
            int[] dp = new int[max];
            Arrays.fill(dp, max);// initial the dp array with amount + 1 which is not valid case.
            dp[0] = 0;//initial amount 0 = 0;
            for (int i = 1; i <= amount; i++) {
                for (int j = 0; j < coins.length; j++) {
                    if (coins[j] <= i) {
                        //the dp[coins[j]] will ba a valid case, then if dp[i - coins[j]] is  valid
                        dp[i] = Math.min(dp[i], dp[i - coins[j]] + 1);
                        // then we update dp[i], otherwise dp[i] = max;
                    }
                }
            }
            return dp[amount] > amount ? -1 : dp[amount];
        }
    }

}

@@ -33,34 +33,8 @@
 s;%0A%0A
-import java.util.Arrays;%0A%0A
 publ
@@ -98,1629 +98,337 @@
     
-public int coinChange(int%5B%5D coins, int amount) %7B%0A            if (amount %3C 1) %7B%0A                return 0;%0A            %7D%0A            int%5B%5D count = new int%5Bamount%5D;%0A            int result = helper(coins, amount, count);%0A            return result;%0A        %7D%0A%0A        //remaining means the remaining coins after the last step;%0A        //count%5Bremaining%5D means the minimum number of coins to sum up to remaining%0A        private int helper(int%5B%5D coins, int remaining, int%5B%5D count) %7B%0A            if (remaining %3C 0) %7B%0A                return -1;//not valid case, thus, per problem description, we should return -1%0A            %7D%0A            if (remaining == 0) %7B%0A                return 0;//completed, this is also a base case for this recursive function%0A            %7D%0A            if (count%5Bremaining - 1%5D != 0) %7B%0A                return count%5Bremaining - 1%5D;//already computed, so reuse it.%0A            %7D%0A            int min = Integer.MAX_VALUE;%0A            for (int coin : coins) %7B%0A                int res = helper(coins, rema
+/**%0A         * credit: https://leetcode.com/problems/coin-change-2/discuss/99212/Knapsack-problem-Java-solution-with-th
 in
+k
 ing
- - coin, count);%0A                if (res %3E= 0 && res %3C min) %7B%0A                    min = 1 + res;%0A                %7D%0A            %7D%0A            return count%5Bremaining - 1%5D = (min == Integer.MAX_VALUE) ? -1 : min;%0A        %7D%0A    %7D%0A%0A    public static class Solution2 %7B%0A        //dp solution%0A        public int coinChange(int%5B%5D coins, int amount) %7B%0A            int max = amount + 1;%0A            int%5B%5D dp = new int%5Bmax%5D;%0A            Arrays.fill(dp, max);// initial the dp array with amount + 1 which is not valid case.%0A            dp%5B0%5D = 0;//initial amount 0 = 0;%0A            for (int i = 1; i %3C= amount; i++
+-process-O(nm)-Time-and-O(m)-Space%0A         */%0A        public int coinChange(int%5B%5D coins, int amount) %7B%0A            int%5B%5D dp = new int%5Bamount + 1%5D;%0A            dp%5B0%5D = 1;%0A            for (int coin : coins
 ) %7B%0A
@@ -456,184 +456,38 @@
 int 
-j = 0; j %3C coins.length; j++) %7B%0A                    if (coins%5Bj%5D %3C= i) %7B%0A                        //the dp%5Bcoins%5Bj%5D%5D will ba a valid case, then if dp%5Bi - coins%5Bj%5D%5D is  valid%0A   
+i = coin; i %3C= amount; i++) %7B%0A
     
@@ -506,32 +506,16 @@
     
- 
 dp%5Bi%5D 
++
 =
- Math.min(dp%5Bi%5D,
  dp%5B
@@ -526,114 +526,11 @@
 coin
-s%5Bj%5D%5D + 1)
+%5D
 ;%0A
-                        // then we update dp%5Bi%5D, otherwise dp%5Bi%5D = max;%0A                    %7D%0A
     
@@ -579,35 +579,8 @@
 turn
- dp%5Bamount%5D %3E amount ? -1 :
  dp%5B

refactor 322