題面：

數據范圍：

$2\le s.length\le 10^5$
$s[i]$ 要么是 ${}^{\prime }{0}^{\prime }$ ，要么是 ${}^{\prime }{1}^{\prime }$
$s[0]==0$
$1\le minJump\le maxJump<s.length$

思路 & Code

重點： 當 $s[i]==0$ 時，才能繼續跳，也才能被跳到。
So，自然會想到存儲所有能夠跳到的 $0$ 點，而當前 $0$ 點必然是從存儲的 $0$ 點跳過來的。容易想到可以暴力狀態轉移。

用一數組 $dp$ 存儲下標狀態：

1. $dp[index]==0$，說明 $index$ 位置沒有被跳到
2. $dp[index]==1$，$index$ 可以被跳到

那么，對于當前點 $index$ 都得判斷 $[min(i?maxJump),0),i?minJump]$ 區間內的所有可跳點，這樣太暴力了，$O(nk)$。必須考慮優化。

差分維護

時間復雜度： $O(n)$
空間復雜度： $O(n)$

維護個前綴和，每次到 $s[i]={=}^{\prime }{0}^{\prime }$（可跳點）時，判斷區間 $[min(i?maxJump),0),i?minJump]$是否存在可跳點 $0$，即 $pre[i?minJump]?pre[i?maxJump?1]$是否大于零。（當然了，區間得注意下）

Code：

bool canReach(string s, int minJump, int maxJump) {int n = s.size();vector<int> dp(n, 0), pre(n, 0);dp[0] = 1;for(int i = 0; i < minJump; ++i) pre[i] = 1;for(int i = minJump; i < n; ++i) {int l = i - maxJump, r = i - minJump;// 差分判斷可跳區間內是否存在 0 點if(s[i] == '0' && pre[r] - (l >= 1 ? pre[l - 1] : 0) > 0) dp[i]=1;pre[i] = pre[i-1] + dp[i];}return dp[n-1];/* 當然了，不用dp數組維護也可以寫成：for(int i = minJump; i < n; ++i) {int l = i - maxJump, r = i - minJump;if(s[i] == '0' && pre[r] - (l >= 1 ? pre[l - 1] : 0) > 0) {if(i == n-1) return true;pre[i] = pre[i-1]+1;} else pre[i] = pre[i-1];}return false;*/
}

當然了，由于可跳區間其實就是一個滑動窗口，直接拿個臨時變量存儲可跳點個數就行，但得存個狀態哈

Code：

bool canReach(string s, int minJump, int maxJump) {int n = s.size(), cnt = 1;vector<bool> dp(n, false);dp[0] = true;for(int i = minJump; i < n; ++ i) {if(s[i] == '0' && cnt) dp[i] = true;// 可跳區間要右移啦（其實就是動態維護滑動窗口的思想啦）// 如果左端點是可跳的，cnt--；如果要加入的點（右端點）是可跳的，cnt++if(i - maxJump >= 0 && dp[i - maxJump]) --cnt;if(i - minJump + 1 < n && dp[i - minJump + 1]) ++ cnt;}return dp[n-1];
}

動態維護滑動窗口（可跳區間）

上面都提到滑動窗口了，那直接拿個隊列去維護滑動窗口也很簡單啦。時間復雜度和空間復雜度都是 $O(n)$。

Code：

bool canReach(string s, int minJump, int maxJump) {int n = s.size();if(s[n-1] == '1') return false;queue<int> q;q.push(0);for(int i = minJump; i < n; ++i) {if(s[i] == '1') continue;while(!q.empty() && q.front() < i - maxJump) q.pop();if(!q.empty() && q.front() <= i - minJump) {if(i == n-1) return true;q.push(i);}}return false;
}