Update Coin Change.java

varunu28 · web-flow · commit 6ef27f17bc73 · 2022-02-11T14:19:12.000-08:00
diff --git a/Medium/Coin Change.java b/Medium/Coin Change.java
@@ -1,29 +1,28 @@
 class Solution {
   public int coinChange(int[] coins, int amount) {
-    if (amount < 1) {
-      return 0;
-    }
-    return coinChange(coins, amount, new int[amount]);
+    Integer[] memo = new Integer[amount + 1];
+    return coinChangeMemoization(coins, amount, memo);
   }
-  
-  private int coinChange(int[] coins, int amount, int[] memo) {
+
+  private int coinChangeMemoization(int[] coins, int amount, Integer[] memo) {
     if (amount < 0) {
       return -1;
     }
     if (amount == 0) {
       return 0;
     }
-    if (memo[amount - 1] != 0) {
-      return memo[amount - 1];
+    if (memo[amount] != null) {
+      return memo[amount];
     }
-    int min = Integer.MAX_VALUE;
+    int minCount = Integer.MAX_VALUE;
     for (int coin : coins) {
-      int res = coinChange(coins, amount - coin, memo);
-      if (res >= 0 && res < min) {
-        min = 1 + res;
+      int count = coinChangeMemoization(coins, amount - coin, memo);
+      if (count == -1) {
+        continue;
       }
+      minCount = Math.min(minCount, count + 1);
     }
-    memo[amount - 1] = min == Integer.MAX_VALUE ? -1 : min;
-    return memo[amount - 1];
+    memo[amount] = minCount == Integer.MAX_VALUE ? -1 : minCount;
+    return memo[amount];
   }
 }

Original file line number	Diff line number	Diff line change
`@@ -1,29 +1,28 @@`
`1`	`1`	`class Solution {`
`2`	`2`	`public int coinChange(int[] coins, int amount) {`
`3`		`- if (amount < 1) {`
`4`		`- return 0;`
`5`		`- }`
`6`		`- return coinChange(coins, amount, new int[amount]);`
	`3`	`+ Integer[] memo = new Integer[amount + 1];`
	`4`	`+ return coinChangeMemoization(coins, amount, memo);`
`7`	`5`	`}`
`8`		`-`
`9`		`- private int coinChange(int[] coins, int amount, int[] memo) {`
	`6`	`+`
	`7`	`+ private int coinChangeMemoization(int[] coins, int amount, Integer[] memo) {`
`10`	`8`	`if (amount < 0) {`
`11`	`9`	`return -1;`
`12`	`10`	`}`
`13`	`11`	`if (amount == 0) {`
`14`	`12`	`return 0;`
`15`	`13`	`}`
`16`		`- if (memo[amount - 1] != 0) {`
`17`		`- return memo[amount - 1];`
	`14`	`+ if (memo[amount] != null) {`
	`15`	`+ return memo[amount];`
`18`	`16`	`}`
`19`		`- int min = Integer.MAX_VALUE;`
	`17`	`+ int minCount = Integer.MAX_VALUE;`
`20`	`18`	`for (int coin : coins) {`
`21`		`- int res = coinChange(coins, amount - coin, memo);`
`22`		`- if (res >= 0 && res < min) {`
`23`		`- min = 1 + res;`
	`19`	`+ int count = coinChangeMemoization(coins, amount - coin, memo);`
	`20`	`+ if (count == -1) {`
	`21`	`+ continue;`
`24`	`22`	`}`
	`23`	`+ minCount = Math.min(minCount, count + 1);`
`25`	`24`	`}`
`26`		`- memo[amount - 1] = min == Integer.MAX_VALUE ? -1 : min;`
`27`		`- return memo[amount - 1];`
	`25`	`+ memo[amount] = minCount == Integer.MAX_VALUE ? -1 : minCount;`
	`26`	`+ return memo[amount];`
`28`	`27`	`}`
`29`	`28`	`}`