Update Perfect Squares.java

varunu28 · web-flow · commit 515e7af20930 · 2021-10-14T09:25:39.000-05:00
diff --git a/Medium/Perfect Squares.java b/Medium/Perfect Squares.java
@@ -1,28 +1,15 @@
 class Solution {
-  Set<Integer> squareNums;
   public int numSquares(int n) {
-    squareNums = new HashSet<>();
-    for (int i = 1; i * i <= n; i++) {
-      squareNums.add(i * i);
-    }
-    int count = 1;
-    for (count = 1; count <= n; count++) {
-      if (isDividedBy(n, count)) {
-        return count;
-      }
-    }
-    return count;
-  }
-  
-  private boolean isDividedBy(int n, int count) {
-    if (count == 1) {
-      return squareNums.contains(n);
-    }
-    for (Integer squareNum : squareNums) {
-      if (isDividedBy(n - squareNum, count - 1)) {
-        return true;
+    int[] dp = new int[n + 1];
+    Arrays.fill(dp, Integer.MAX_VALUE);
+    dp[0] = 0;
+    for(int i = 1; i <= n; i++) {
+      int min = Integer.MAX_VALUE;
+      for (int j = 1; i - j * j >= 0; j++) {
+        min = Math.min(min, dp[i - j * j] + 1);
       }
+      dp[i] = min;
     }
-    return false;
+    return dp[n];
   }
 }
