b_lc_跳跃游戏 vii（前缀和 + dp）

一开始，你在下标 0 处，且该位置的值一定为 ‘0‘ 。当同时满足如下条件时，你可以从下标 i 移动到下标 j 处：

• i + minJump <= j <= min(i + maxJump, s.length - 1) 且
• s[j] == ‘0‘.

如果你可以到达 s 的下标 s.length - 1 处，请你返回 true ，否则返回 false 。

思路：一般都是向后 x 个单位看某个点 j，如果 j 能到达，则当前位置 i 可达.
f[i] 表示i是否可达，pre[i]表示f的前缀和，只要区间 [i-maxjump, i-minjump] 中有一个位置可达，则 i 可达

class Solution:
    def canReach(self, s: str, a: int, b: int) -> bool:
        n = len(s)
        pre = [0] * (n + 1)
        f = [False] * (n + 1)
        pre[1] = f[1] = 1

        for i in range(1, n + 1):
            if s[i-1] == ‘0‘:
                l = max(0, i - b)
                r = max(0, i - a)
                if r >= 1 and pre[r] - pre[l - 1] > 0:
                    f[i] = True
            pre[i] = pre[i-1] + f[i]
        return f[n]

b_lc_跳跃游戏 vii（前缀和 + dp）

原文：https://www.cnblogs.com/wdt1/p/14853795.html