add a solution for 279

fishercoder1534 · fishercoder1534 · commit f7f94b257477 · 2021-10-14T08:05:15.000-07:00
diff --git a/src/main/java/com/fishercoder/solutions/_279.java b/src/main/java/com/fishercoder/solutions/_279.java
@@ -37,4 +37,35 @@ public int numSquares(int n) {
         }
     }
 
+    public static class Solution3 {
+        /**
+         * My completely original DP solution on 10/14/2021.
+         * <p>
+         * Again, once you use a pen and paper to visualize your thought process, the idea flows out very quickly.
+         * Thinking without a pen and paper is a waste of time in most cases! :)
+         */
+        public int numSquares(int n) {
+            int[] dp = new int[n + 1];
+            for (int i = 1; i <= n; i++) {
+                int x = (int) Math.sqrt(i);
+                if (Math.pow(x, 2) == i) {
+                    dp[i] = 1;
+                } else {
+                    dp[i] = i;
+                    int left = 1;
+                    int right = i - 1;
+                    while (left < right) {
+                        dp[i] = Math.min(dp[i], dp[left] + dp[right]);
+                        left++;
+                        right--;
+                    }
+                    if (left == right && i % left == 0) {
+                        dp[i] = Math.min(dp[i], (i / left) * dp[left]);
+                    }
+                }
+            }
+            return dp[n];
+        }
+    }
+
 }
diff --git a/src/test/java/com/fishercoder/_279Test.java b/src/test/java/com/fishercoder/_279Test.java
@@ -0,0 +1,31 @@
+package com.fishercoder;
+
+import com.fishercoder.solutions._279;
+import com.fishercoder.solutions._340;
+import org.junit.BeforeClass;
+import org.junit.Test;
+
+import static org.junit.Assert.assertEquals;
+
+public class _279Test {
+    private static _279.Solution1 solution1;
+    private static _279.Solution2 solution2;
+    private static _279.Solution3 solution3;
+
+    @BeforeClass
+    public static void setup() {
+        solution1 = new _279.Solution1();
+        solution2 = new _279.Solution2();
+        solution3 = new _279.Solution3();
+    }
+
+    @Test
+    public void test1() {
+        int n = 9;
+        int expected = 1;
+        assertEquals(expected, solution1.numSquares(n));
+        assertEquals(expected, solution2.numSquares(n));
+        assertEquals(expected, solution3.numSquares(n));
+    }
+
+}
