refactor 198

fishercoder1534 · fishercoder1534 · commit 2ed76618ffa2 · 2021-09-14T08:14:35.000-07:00
diff --git a/src/main/java/com/fishercoder/solutions/_198.java b/src/main/java/com/fishercoder/solutions/_198.java
@@ -1,5 +1,7 @@
 package com.fishercoder.solutions;
 
+import java.util.Arrays;
+
 public class _198 {
 
     public static class Solution1 {
@@ -10,9 +12,6 @@ public int rob(int[] nums) {
             if (nums.length == 1) {
                 return nums[0];
             }
-            if (nums.length == 2) {
-                return Math.max(nums[0], nums[1]);
-            }
             int[] dp = new int[nums.length];
             dp[0] = nums[0];
             dp[1] = Math.max(nums[0], nums[1]);
@@ -22,4 +21,29 @@ public int rob(int[] nums) {
             return dp[nums.length - 1];
         }
     }
+
+    public static class Solution2 {
+        /**
+         * recursion + memoization, basically the same as the above solution1
+         * credit: https://leetcode.com/problems/house-robber/solution/
+         */
+        int[] memo;
+
+        public int rob(int[] nums) {
+            memo = new int[nums.length];
+            Arrays.fill(memo, -1);
+            return robFrom(0, nums);
+        }
+
+        private int robFrom(int start, int[] nums) {
+            if (start >= nums.length) {
+                return 0;
+            }
+            if (this.memo[start] != -1) {
+                return this.memo[start];
+            }
+            this.memo[start] = Math.max(robFrom(start + 1, nums), robFrom(start + 2, nums) + nums[start]);
+            return this.memo[start];
+        }
+    }
 }
diff --git a/src/test/java/com/fishercoder/_198Test.java b/src/test/java/com/fishercoder/_198Test.java
@@ -0,0 +1,30 @@
+package com.fishercoder;
+
+import com.fishercoder.solutions._198;
+import org.junit.BeforeClass;
+import org.junit.Test;
+
+import static org.junit.Assert.assertEquals;
+
+public class _198Test {
+    private static _198.Solution1 solution1;
+    private static _198.Solution2 solution2;
+
+    @BeforeClass
+    public static void setup() {
+        solution1 = new _198.Solution1();
+        solution2 = new _198.Solution2();
+    }
+
+    @Test
+    public void test1() {
+        assertEquals(4, solution1.rob(new int[]{1, 2, 3, 1}));
+        assertEquals(4, solution2.rob(new int[]{1, 2, 3, 1}));
+    }
+
+    @Test
+    public void test2() {
+        assertEquals(4, solution1.rob(new int[]{2, 1, 1, 2}));
+    }
+
+}
