Python - different approaches with explanations
Approach 1: count the number of ways it can reach the last index from the origin (TLE)\nLet k = maxJump - minJump, N is the length of the string\nTime Complexci
**Approach 1: count the number of ways it can reach the last index from the origin (TLE)**\nLet k = maxJump - minJump, N is the length of the string\nTime Complexcity: `O(Nk)` \n```\ndef canReach(s, minJump, maxJump):\n    n = len(s)\n    dp = [0] * n\n    dp[0] = 1\n    for i in range(1, n):\n        if s[i] == \'1\':continue\n        for j in range(max(0, i-maxJump), i-minJump+1):\n            dp[i] += dp[j]\n    print(dp)\n    return dp[-1] > 0\n```\n---\nSide question: \nOn x-axis, how many ways you can reach N from 1?\nIn other words, how many ways you can go to 5 from 1? \n1,2,3,4,5 \n1,2,X,4,5\n1,2,3,X,5\n1,2,X,X,5\n1,X,3,4,5\n1,X,3,X,5\n1,X,X,4,5\n1,X,X,X,5\nIn total, there are 8 ways.\nYou can observe there are $$2^{n-2}$$ ways to travel from $$1,...,N$$ nodes. The middle part is actually the binary representation(Power Set).\nThe idea of DP comes from here. Let dp[i] means the number of ways we can reach i from 1.\nInitially, dp[1] = 1, dp[2] = 1\nWhat\'s dp[3]? we just need to add up all the previous answers. If we know dp[1] and dp[2], then we can make use of these information. dp[3] = dp[1] + dp[2].\nLook at above example, if I rearrange them.\nThis is the number of ways from 1 to 4 only\n1,2,3,4\n1,2,X,4\n1,X,3,4\n1,X,X,4\nThis is the number of ways from 1 to 3 only\n1,2,3,X\n1,X,3,X\nThis is the number of ways from 1 to 2 only\n1,2,X,X\nThis is the number of ways from 1 to 1 only\n1,X,X,X\nIf we want to know dp[5], we just need to add 5 to the end of all these answers.\n\n---\n\n**Approach 2: Improvement on Approach 1**\nuse 0 or 1 to represent reacheable, once you know there\'s way to reach i, that\'s it. so you don\'t need to store the total number of ways\nTime Complexcity: `O(Nk)`  Although it\'s faster but in worse case it is the same as Approach 1.\n\n```\ndef canReach(s, minJump, maxJump):\n    n = len(s)\n    dp = [0] * n\n    dp[0] = 1\n    for i in range(1, n):\n        if s[i] == \'1\':continue\n        for j in range(max(0, i-maxJump), i-minJump+1):\n            if dp[j] == 1:\n                dp[i] = 1\n                break\n    print(dp)\n    return dp[-1] > 0\n```\n\n**Approach 3: Improvement on Approach 1 with partial sum**\nLike approach 1, when we are at index `i`, we need to calculate the sum of dp[A:B] where A = max(0, i-maxJump), B = i-minJump. If we have an array with accumulated sum `ps`, then partial sum can be done in O(1)\nTime Complexcity: `O(N)`\npartial sum of dp[A:B] = ps[B] - ps[A-1], why minus 1 here?\nSuppose, we have \ndp = [1, 1, 2, 4, 8]\nps = [1, 2, 4, 8, 16]\nwe want to calcualte sum of dp[2:3], it is equal to ps[3] - ps[2-1]\n\nHowever, this gets MLE(memory limit exceeded) because numbers grow too big. Even though python can handle very large number, it takes memories to store.\n\n```\ndef canReach(s, minJump, maxJump):\n    n = len(s)\n    dp, ps = [0] * n, [0] * n\n    dp[0], ps[0] = 1, 1\n    for i in range(1, n):\n        if s[i] == \'1\': \n            ps[i] = ps[i-1]\n        else:\n            left = 0 if i-maxJump-1 < 0 else ps[i-maxJump-1]\n            right = 0 if i-minJump < 0 else ps[i-minJump]\n            diff = right - left\n            dp[i] = diff\n            ps[i] = ps[i-1] + dp[i]\n    return dp[-1] > 0\n```\n**Approach 4: Improvement on Approach 3 with Approach 2**\nUse the idea in Approach 2, we can deal with the big numbers.\nAs `dp` only consists of 0 and 1. The accumulated sum array `ps` can only be as big as N.\nFor example: this is the worse case.\ndp = [1,1,1,1,1]\nps = [1,2,3,4,5]\nTime Complexity: O(N)\n```\ndef canReach(s, minJump, maxJump):\n    n = len(s)\n    dp, ps = [0] * n, [0] * n\n    dp[0], ps[0] = 1, 1\n    for i in range(1, n):\n        if s[i] == \'1\': \n            ps[i] = ps[i-1]\n        else:\n            left = 0 if i-maxJump-1 < 0 else ps[i-maxJump-1]\n            right = 0 if i-minJump < 0 else ps[i-minJump]\n            diff = right - left\n            dp[i] = 1 if diff > 0 else 0\n            ps[i] = ps[i-1] + dp[i]\n    return dp[-1] > 0\n```\n**Approach 5: Improvement on Approach 4 with sliding window**\nYou can stop here. O(N) is the fastest already. We can get rid of `ps` array by keeping a sliding window. This saves some memory.\nTime Complexcity: O(N)\n```\ndef canReach(s, minJump, maxJump):\n    n = len(s)\n    dp = [0] * n\n    dp[0]= 1\n    diff = 0\n    for i in range(1, n):\n        left = i-maxJump-1\n        right = i-minJump\n        # print(\'i\',i, left, right, dp[left:right])\n        if right >= 0 : diff += dp[right]\n        if left >= 0 : diff -= dp[left]\n        if s[i] == \'0\':\n            dp[i] = 1 if diff > 0 else 0\n        # print(dp, diff)\n    return dp[-1] > 0\n```\n\n**Approach 6: look forward DP**\n```\nTime Complexcity: O(Nk)\nInstead of lookback, we can look forward.\ndef canReach(s, minJump, maxJump):\n    n = len(s)\n    dp = [0] * n\n    dp[0]= 1\n    for i in range(n):\n        if dp[i] == 1:\n            j = i + minJump\n            while j < min(n-1, i+maxJump)+1):\n                if s[j] == \'0\':\n                    if j == n - 1:\n                        return True\n                    dp[j] = 1\n    print(dp)\n    return dp[-1] > 0\n```\n\n**Approach 7: look forward DP**\n\nWe can keep track of the maximum index we have visited. The idea is that if an index is visited, no need to visit it again.\nTime Complexcity: O(N)\n```\ndef canReach(s, minJump, maxJump):\n    n = len(s)\n    dp = [0] * n\n    dp[0]= 1\n    j = 0\n    for i in range(n):\n        if dp[i] == 1:\n            # the only difference from approach 6\n            j = max(j, i+minJump)\n            while j < min(n-1, i+maxJump)+1:\n                if s[j] == \'0\':\n                    if j == n - 1:\n                        return True\n                    dp[j] = 1\n                j += 1\n    return dp[-1] > 0\n```
[]