add a solution for 55

fishercoder1534 · fishercoder1534 · commit 515724f2645d · 2021-09-16T11:48:59.000-07:00
diff --git a/src/main/java/com/fishercoder/solutions/_55.java b/src/main/java/com/fishercoder/solutions/_55.java
@@ -52,7 +52,7 @@ public static class Solution3 {
          * Top-down DP.
          * Credit: https://leetcode.com/problems/jump-game/solution/ approach 2
          * <p>
-         * Specifically, for this problem, my very own Solution1 and the above Solution2 run much faster than this DP solution.
+         * Specifically, for this problem, my very own Solution1 and the above Solution2 run much faster than this DP solution, likely due to this is top-down, there's stack overhead.
          * But just use this problem to practice DP.
          * <p>
          * The reason it's called top-down is that it's filling the dp array from the right to the left if you set break points and step through this.
@@ -79,4 +79,26 @@ private boolean canJumpFrom(int index, int[] nums, int[] dp) {
             return false;
         }
     }
+
+    public static class Solution4 {
+        /**
+         * This is bottom-up DP.
+         */
+        public boolean canJump(int[] nums) {
+            int[] dp = new int[nums.length];
+            //0 means unknown, 1 means reachable, 2 means unreachable
+            dp[nums.length - 1] = 1;
+            for (int i = nums.length - 2; i >= 0; i--) {
+                int furthestReach = Math.min(nums[i] + i, nums.length - 1);
+                for (int j = i + 1; j <= furthestReach; j++) {
+                    if (dp[j] == 1) {
+                        dp[i] = 1;
+                        break;
+                    }
+                }
+            }
+            return dp[0] == 1;
+        }
+
+    }
 }
diff --git a/src/test/java/com/fishercoder/_55Test.java b/src/test/java/com/fishercoder/_55Test.java
@@ -10,13 +10,15 @@ public class _55Test {
     private static _55.Solution1 solution1;
     private static _55.Solution2 solution2;
     private static _55.Solution3 solution3;
+    private static _55.Solution4 solution4;
     private static int[] nums;
 
     @BeforeClass
     public static void setup() {
         solution1 = new _55.Solution1();
         solution2 = new _55.Solution2();
         solution3 = new _55.Solution3();
+        solution4 = new _55.Solution4();
     }
 
     @Test
@@ -25,6 +27,7 @@ public void test1() {
         assertEquals(false, solution1.canJump(nums));
         assertEquals(false, solution2.canJump(nums));
         assertEquals(false, solution3.canJump(nums));
+        assertEquals(false, solution4.canJump(nums));
     }
 
     @Test
@@ -33,6 +36,7 @@ public void test2() {
         assertEquals(true, solution1.canJump(nums));
         assertEquals(true, solution2.canJump(nums));
         assertEquals(true, solution3.canJump(nums));
+        assertEquals(true, solution4.canJump(nums));
     }
 
     @Test
@@ -41,6 +45,7 @@ public void test3() {
         assertEquals(true, solution1.canJump(nums));
         assertEquals(true, solution2.canJump(nums));
         assertEquals(true, solution3.canJump(nums));
+        assertEquals(true, solution4.canJump(nums));
     }
 
     @Test
@@ -49,6 +54,7 @@ public void test4() {
         assertEquals(true, solution1.canJump(nums));
         assertEquals(true, solution2.canJump(nums));
         assertEquals(true, solution3.canJump(nums));
+        assertEquals(true, solution4.canJump(nums));
     }
 
     @Test
@@ -57,6 +63,7 @@ public void test5() {
         assertEquals(true, solution1.canJump(nums));
         assertEquals(true, solution2.canJump(nums));
         assertEquals(true, solution3.canJump(nums));
+        assertEquals(true, solution4.canJump(nums));
     }
 
     @Test
@@ -65,6 +72,7 @@ public void test6() {
         assertEquals(true, solution1.canJump(nums));
         assertEquals(true, solution2.canJump(nums));
         assertEquals(true, solution3.canJump(nums));
+        assertEquals(true, solution4.canJump(nums));
     }
 
     @Test
@@ -73,6 +81,7 @@ public void test7() {
         assertEquals(false, solution1.canJump(nums));
         assertEquals(false, solution2.canJump(nums));
         assertEquals(false, solution3.canJump(nums));
+        assertEquals(false, solution4.canJump(nums));
     }
 
     @Test
@@ -81,14 +90,16 @@ public void test8() {
         assertEquals(true, solution1.canJump(nums));
         assertEquals(true, solution2.canJump(nums));
         assertEquals(true, solution3.canJump(nums));
+        assertEquals(true, solution4.canJump(nums));
     }
 
     @Test
     public void test9() {
         nums = new int[]{3, 2, 1, 0, 4};
-//        assertEquals(false, solution1.canJump(nums));
-//        assertEquals(false, solution2.canJump(nums));
+        assertEquals(false, solution1.canJump(nums));
+        assertEquals(false, solution2.canJump(nums));
         assertEquals(false, solution3.canJump(nums));
+        assertEquals(false, solution4.canJump(nums));
     }
 
 
