[Python] O(n) DP with sliding window partial sum and explanation included
In order to understand the sliding window with partial sum solution, I think it is first helpful to understand the brute force O(n^2) DP solution. Technically, 
In order to understand the sliding window with partial sum solution, I think it is first helpful to understand the brute force O(n^2) DP solution. Technically, it is O(n * (maxJump - minJump)), but worst case maxJump-minJump could be up to n.\n\n```\nclass Solution:\n    def canReach(self, s: str, minJump: int, maxJump: int) -> bool:\n\t\t# dp[i] represents whether i is reachable\n        dp = [False for _ in s]\n        dp[0] = True\n\n        for i in range(1, len(s)):\n            if s[i] == "1":\n                continue\n\n\t\t\t# iterate through the solutions in range [i - maxJump, i - minJump]\n\t\t\t# and if any previous spot in range is reachable, then i is also reachable\n            window_start = max(0, i - maxJump)\n            window_end = i - minJump\n            for j in range(window_start, window_end + 1):\n                if dp[j]:\n                    dp[i] = True\n                    break\n        \n        return dp[-1]       \n\n```\n\nBelow is the optimized O(n) solution with the partial sum sliding window optimization.\n```\nclass Solution:\n    def canReach(self, s: str, minJump: int, maxJump: int) -> bool:\n        # One pass dynamic programming with sliding window\n        #\n        # The general idea is the same as the brute force\n        # bottom-up dynamic programming solution, but instead of\n        # always looping through all the previous reachable spots,\n        # we maintain a partial sum that counts the number of previous \n        # reachable spots in the sliding window [i - maxJump, i - minJump].\n        # \n        # O(n) time complexity one pass\n        # O(n) space complexity for dp array\n\n        # dp[i] represents whether i is reachable\n        dp = [False for _ in s]\n        dp[0] = True\n\n        # num_prev_reachable counts the number of previous spots\n        # within the sliding window [i - maxJump, i - minJump]\n        # that we can jump from to reach i\n        num_prev_reachable = 0\n\n        for i in range(1, len(s)):\n            # the sliding window left bound is being updated to i - maxJump\n            # the sliding window right bound is being updated to i - minJump\n            \n            # exclude previous reachable spot (prev left bound)\n            if i > maxJump and dp[i - maxJump - 1]:\n                num_prev_reachable -= 1\n            # include new reachable spot (new right bound)\n            if i >= minJump and dp[i - minJump]:\n                num_prev_reachable += 1\n            \n            # if we can reach this 0 from prev reachable spots, it is reachable\n            if s[i] == "0" and num_prev_reachable > 0:\n                dp[i] = True\n\n        return dp[-1]\n```
['Dynamic Programming', 'Sliding Window', 'Python']