Java | DP solutions: Bottom-Up Backward, Forward, and Top-Down
Approach 1. (Backward) Quadratic DP (TLE)\n\nWe can start with a "brute force", quadratic time DP, of the standard type: "counting the number of ways" in which 
**Approach 1. (Backward) Quadratic DP (TLE)**\n\nWe can start with a "brute force", quadratic time DP, of the standard type: **"counting the number of ways"** in which we can get to the final index.\nFor each index *i* we check if it contains a *0*, if so we look back to the window of indexes *[j, j2]* that a jump to *i* could have originated from, and sum up the values in those indexes. This is short and easy, works for small test cases, but unsurprisingly it TLEs for larger ones.\n```\n    public boolean canReach(String s, int minJump, int maxJump) {\n        int n= s.length(), dp[]= new int[n];\n        dp[0]= 1;\n        for(int i=1; i<n; i++){\n            if(s.charAt(i)==\'1\') continue;\n            for(int j=Math.max(0, i-maxJump), j2=i-minJump; j<=j2; j++)\n\t\t\t\tdp[i]+= dp[j];\n        }\n\t\treturn dp[n-1]>0;\n\t}\n```\n**Approach 2.  (Backward) Linear DP usign Partial Sum (WA/overflow or MLE with BigInteger)**\n\nThe internal for loop is doing an interval sum, which we can do in O(1) using partial sum. However, this runs into a different problem: Wrong Answer due to int overflow (you can print the final dp[] array to see some large negative numbers). Moving to long type does not help, the numbers get very big, very fast in certain test cases. Even trying to brute force it by moving to BigInteger will not help us as Leetcode will respond with a rarer MLE (Memory Limit Exceeded). We could think of trying to work around it with some modulo arithmetics or.. we could think again if we are solving the right problem.\n```\n    public boolean canReach(String s, int minJump, int maxJump) {\n        int n= s.length(), dp[]= new int[n], ps[]= new int[n];\n        dp[0]= 1;\n        ps[0]= 1;\n        for(int i=1; i<n; i++){\n            if(s.charAt(i)==\'1\'){\n                ps[i]= ps[i-1];\n            }else{\n                int j= i-maxJump-1, j2= i-minJump;\n                dp[i]= (j2<0 ? 0 : ps[j2])-(j<0 ? 0 : ps[j]);\n                ps[i]= ps[i-1] + dp[i];\n            }\n        }\n\t\t//System.out.println(Arrays.toString(dp));  // uncomment to see overflow for failed test cases\n        return dp[n-1]>0;\n    }\n```\n**Approach 3.  (Backward) Quadratic DP (2387ms, 5%, Accepted) marking reachable positions**\n\nTo avoid the huge numbers problem, rather than representing "ways" to reach the i-th index (which is unnecessary, as we\'re solving a simpler problem here) we take a step back to the quadratic DP but use the dp[] array just to represent whether we can reach the index (1) or not (0), a **"yes/no decision"** DP problem. This actually gets accepted by Leetcode already (although it\'s very slow)\n```    \n\tpublic boolean canReach(String s, int minJump, int maxJump) {\n        int n= s.length(), dp[]= new int[n];\n        dp[0]= 1;\n        for(int i=1; i<n; i++){\n            if(s.charAt(i)==\'1\') continue;\n            for(int j=Math.max(0, i-maxJump), j2=i-minJump; j<=j2; j++)\n\t\t\t\t   if(dp[j]==1){ dp[i]= 1; break; } // this line is the only difference vs. Approach 1\n        }\n        return dp[n-1]>0;\n    }\n```\n**Approach 4.  (Backward) Linear DP (8ms, 92%, Accepted) marking reachable positions with Partial Sum**\n\nAs with Approach 2., we can improve Approach 3 using partial sums and get to a very fast O(N) solution,\n```    \n\tpublic boolean canReach(String s, int minJump, int maxJump) {\n        int n= s.length(), dp[]= new int[n], ps[]= new int[n];\n        dp[0]= 1;\n        ps[0]= 1;\n        for(int i=1; i<n; i++){\n            if(s.charAt(i)==\'1\'){\n                ps[i]= ps[i-1];\n            }else{\n                int j= i-maxJump-1, j2= i-minJump;\n                int psDiff= (j2<0 ? 0 : ps[j2]) - (j<0 ? 0 : ps[j]);\n                dp[i]= psDiff > 0 ? 1 : 0;  // the only difference vs. Approach 2 - dp[] now just has binary values 0 or 1\n                ps[i]= ps[i-1] + dp[i];\n            }\n        }\n        return dp[n-1]>0;\n    }\n```\n\n**Approach 5.  (Backward) Linear DP (8ms, 92%, Accepted) marking reachable positions with Sliding Window**\n\nWe could stop here as Approach 4. is a perfectly acceptable solution with O(N) time and O(N) space. What we\'re doing next is just improving the "constant" in front of the linear space complexity.\nWe may notice that the partial sum difference calculated in Approach 4 is essentially a sum of the reachable indexes within a constant-size sliding window; we can save some memory by removing the ps[] array and replace it with a single number.\n```\n    public boolean canReach(String s, int minJump, int maxJump) {\n        int n= s.length(), dp[]= new int[n], psDiff= 0;\n        dp[0]= 1;\n        for(int i=1; i<n; i++){\n            int j= i-maxJump-1, j2= i-minJump;\n            if(j2>-1) psDiff+= dp[j2];\n            if(j>-1) psDiff-= dp[j];\n            if(s.charAt(i)==\'0\')\n\t\t\t\tdp[i]= psDiff>0 ? 1 : 0;\n        }\n        return dp[n-1]>0;\n    }\n```\n**Approach 5B.  (Backward) Linear DP (8ms, 92%, Accepted) marking reachable positions with Sliding Window**\nThis is not a separate approach, but we simply replace the int dp[] array with boolean dp[] array to get to...  [@lee215](https://leetcode.com/lee215)\'s solution:\nhttps://leetcode.com/problems/jump-game-vii/discuss/1224804/JavaC%2B%2BPython-One-Pass-DP\n```\npublic boolean canReach(String s, int minJump, int maxJump) {\n        int n= s.length(), psDiff= 0;\n        boolean[] dp= new boolean[n];\n        dp[0]= true;\n        for(int i=1; i<n; i++){\n            int j= i-maxJump-1, j2= i-minJump;\n            if(j2>-1 && dp[j2]) psDiff++;\n            if(j>-1 && dp[j]) psDiff--;\n            if(s.charAt(i)==\'0\')\n                dp[i]= psDiff>0;\n        }\n        return dp[n-1];\n    }\n```\n**Approach 6. Forward Quadratic DP (TLE)**\nThis approach is different, as it uses the forward dynamic programming approach - we derive all the subsequent positions reachable from the current position. Coding is simple, but unsurprisingly we run into a TLE again for larger test cases, due to the inner for loop making the time complexity of the solution quadratic.\n```\n    boolean canReach(String s, int minJump, int maxJump) {\n        int n=s.length();\n\t\tboolean[] dp= new boolean[n];\n        dp[0]= true;\n        for(int i=0, j=0; i<n; ++i) \n            if(dp[i])\n                for(j= i+minJump; j<=Math.min(n-1, i+maxJump); ++j)\n                    if(s.charAt(j)==\'0\') {\n                        if(j==n-1) return true; \n                        dp[j]= true;\n                }\n        return false;\n    } \n```\t\n**Approach 7. Forward Linear DP (7ms, 94%, Accepted)**\nWe can improve Approach 6 by noticing something crucially infefficient about it: its inner loop repeatedly visits many of the same forward indices. We can avoid that by keeping track of the maximum index we have already visited and not revisit it again as the next state. This gives us the simplest and the fastest (linear time complexity) solution yet!\n```\n    boolean canReach(String s, int minJump, int maxJump) {\n        int n=s.length();\n\t\tboolean[] dp= new boolean[n];\n        dp[0]= true;\n        for(int i=0, j=0; i<n; ++i) \n            if(dp[i])\n                for(j= Math.max(j, i+minJump); j<=Math.min(n-1, i+maxJump); ++j)  // the only difference to Approach 6. is Math.max(j, i+minJump)\n                    if(s.charAt(j)==\'0\') {\n                        if(j==n-1) return true; \n                        dp[j]= true;\n                }\n        return false;\n    } \n```\t\n**Bonus: Approach 4B. Top-down Linear DP  with memoization (74ms, 22%, Accepted)**\nOn request - this is Approach 4 rewritten as a top-down solution.\nA recursive implementation of partial sums is not the most intutive thing to do, the bottom-up approach is much more natural.\nHowever, this top-down solution is still much much faster than the naive bottom-up quadratic DP, and gets Accepted comfortably.\n```\nclass Solution {\n    public boolean canReach(String s, int minJump, int maxJump) {\n        int n= s.length();\n        int[] dp= new int[n], ps= new int[n];\n        Arrays.fill(dp, -1);\n        Arrays.fill(ps, -1);\n        int res= canReach(s, minJump, maxJump, n-1, dp, ps);\n        return res>0;\n    }\n    \n    private int canReach(String s, int minJump, int maxJump, int i, int[] dp, int[] ps){\n        if(dp[i]!=-1) return dp[i];\n        if(i==0) return dp[i]= 1;\n        if(s.charAt(i)==\'1\') return dp[i]= 0;\n        int j= i-maxJump-1, j2= i-minJump;\n        int psDiff= (j2<0 ? 0 : partialSum(s, minJump, maxJump, j2, dp, ps)) \n            - (j<0 ? 0 : partialSum(s, minJump, maxJump, j, dp, ps));\n        return dp[i]= psDiff > 0 ? 1 : 0;\n    }\n    \n    private int partialSum(String s, int minJump, int maxJump, int i, int[] dp, int[] ps){\n        if(ps[i]!=-1) return ps[i];\n        if(i==0) return ps[i]= 1;\n        return ps[i]= partialSum(s, minJump, maxJump, i-1, dp, ps)\n                    + (s.charAt(i)==\'1\' ? 0 : canReach(s, minJump, maxJump, i, dp, ps));\n    }\n}\n```\n**Bonus2. Approach 3B. Top-down Quadratic DP (TLE)**\nFor completeness, Approach 3 rewritten as top-down DP (as it\'s an easier step towards Approach 4B). It only works for small tests cases, otherwise it TLEs.\n```\nclass Solution {\n    public boolean canReach(String s, int minJump, int maxJump) {\n        int n= s.length();\n        int[] dp= new int[n];\n        Arrays.fill(dp, -1);\n        return canReach(s, minJump, maxJump, n-1, dp)==1;\n    }\n    \n    private int canReach(String s, int minJump, int maxJump, int i, int[] dp){\n        if(dp[i]!=-1) return dp[i];\n        if(i==0) return dp[i]= 1;\n        if(s.charAt(i)==\'1\') return dp[i]= 0;\n        for(int j=Math.max(0, i-maxJump), j2=i-minJump; j<=j2; j++)\n            if(canReach(s, minJump, maxJump, j, dp)==1) return dp[i]= 1;\n        return dp[i]= 0;\n    }\n}\n```
[]