1871. 跳跃游戏 VII：用滑动窗口优化可达性 DP

令 dp[i] 表示能否到达位置 i。当 s[i] 为 0 时，若区间 [i - maxJump, i - minJump] 中任意位置可达，则 dp[i] 为真。

暴力 DP#

以下是原始的区间枚举版本：

1
class Solution {
2
public:
3
    bool canReach(string s, int minJump, int maxJump) {
4
        int n = s.size();
5
        vector<int> f(n, 0);
6

7
        f[0] = 1;
8

9
        for(int i = 0; i < n; i ++ ) {
10
            if(!f[i]) continue;
11

12
            for(int j = i + minJump; j <= min(n - 1, i + maxJump); j ++ ) {
13
                if(s[j] == '0') f[j] = 1;
14
            }
15
        }
16

17
        return f[n - 1];
18
    }
19
};

直接检查整个区间需要 $O(n^2)$ 。观察到该区间随 i 右移，维护窗口内可达位置数 count 即可。

滑动窗口优化#

1
class Solution {
2
public:
3
    bool canReach(string s, int minJump, int maxJump) {
4
        int n = s.size();
5

6
        vector<int> f(n, 0);
7
        f[0] = 1;
8

9
        int cnt = 0;
10
        for(int i = 1; i < n; i ++ ) {
11

12
            int r = i - minJump;
13
            if(r >= 0 && f[r]) cnt ++;
14

15
            int l = i - maxJump - 1;
16
            if(l >= 0 && f[l]) cnt --;
17

18
            if(s[i] == '0' && cnt) f[i] = 1;
19
        }
20

21
        return f[n - 1];
22
    }
23
};

enter 是新进入可跳区间的位置，leave 是刚离开区间的位置；两者的下标是最容易写错的部分。时间复杂度 $O(n)$ ，空间复杂度 $O(n)$ 。