1871. Jump Game VII

題目 / Problem

給你一個 0-indexed（下標從 0 開始）的二進位字串 s，以及兩個整數 minJump 和 maxJump。一開始你站在下標 0，而 s[0] 保證是 '0'。你可以從下標 i 跳到下標 j，前提是同時滿足：

i + minJump <= j <= min(i + maxJump, s.length - 1)（跳躍距離落在 [minJump, maxJump] 之間，且不超出字串末端），且
s[j] == '0'（只能落在值為 '0' 的位置上）。

問：能否最終到達最後一個下標 s.length - 1？能則回傳 true，否則 false。

You are given a 0-indexed binary string s and two integers minJump and maxJump. You start at index 0, where s[0] == '0'. From index i you may jump to index j if i + minJump <= j <= min(i + maxJump, s.length - 1) and s[j] == '0'. Return true if you can reach the last index s.length - 1, otherwise false.

Constraints / 限制 - 2 <= s.length <= 10^5 - s[i] 是 '0' 或 '1' - s[0] == '0' - 1 <= minJump <= maxJump < s.length

Example / 範例

Input:  s = "011010", minJump = 2, maxJump = 3
Output: true
解釋 / Explanation: 0 → 3（跳 3 步），再 3 → 5（跳 2 步），到達末端下標 5。

名詞解釋 / Glossary

動態規劃 / Dynamic Programming (DP)：把大問題拆成許多小問題，記錄每個小問題的答案後重複利用。這裡我們用 dp[i] 記錄「下標 i 是否可達」。 / Break a big problem into smaller subproblems, store each subproblem's answer and reuse it. Here dp[i] stores whether index i is reachable.
布林陣列 / Boolean array：每個元素只有 true/false 兩種值的陣列。 / An array where each element is either true or false.
滑動視窗 / Sliding window：一段隨著掃描而左右移動的連續區間。對下標 i，能跳到它的前驅位置正好落在區間 [i-maxJump, i-minJump]，這就是視窗。 / A contiguous range that slides as we scan. For index i, the predecessors that can jump to it lie exactly in [i-maxJump, i-minJump] — that range is the window.
前綴和 / Prefix sum (running count)：邊掃描邊維護一個累計數量，避免每次都重新數一遍。這裡用它記錄「視窗內有幾個可達位置」。 / A count maintained incrementally while scanning, so we never recount from scratch. Here it tracks how many reachable indices are inside the window.
指標解引用 / Pointer dereference (C)：s 是指向字元的指標，s[i] 等同於「讀取第 i 個字元」。 / In C, s is a pointer to characters; s[i] reads the i-th character.

思路

最直接的想法是暴力動態規劃：設 dp[i] 表示能否到達下標 i。對每個 i，回頭檢查區間 [i-maxJump, i-minJump] 裡有沒有任何一個可達的位置 j，若有且 s[i]=='0'，則 dp[i]=true。但這樣每個 i 都要掃一整段區間，最壞情況下總工作量是 O(n × maxJump)，當 n 達到 10^5 且跳躍範圍很大時會超時。問題的關鍵在於：我們並不需要知道區間裡「具體哪一個」位置可達，只需要知道「至少有一個」可達就夠了——這正是計數問題。於是引入滑動視窗加前綴和：維護一個變數 pre，代表當前下標對應的前驅區間 [i-maxJump, i-minJump] 內有多少個可達位置。每往右走一步 i，視窗的右端新增 dp[i-minJump]（把它加進 pre），左端的 dp[i-maxJump-1] 滑出視窗（從 pre 減掉）。這樣每步只做 O(1) 的加減，總複雜度降到 O(n)。對每個 i，只要 s[i]=='0' 且 pre>0（視窗裡有可達前驅），就標記 dp[i]=true。最後回傳 dp[n-1]。

The naive idea is a brute-force DP: let dp[i] mean "index i is reachable." For each i, look back over the range [i-maxJump, i-minJump] and check whether any reachable index exists there; if one does and s[i]=='0', set dp[i]=true. But scanning the whole range for every i costs O(n × maxJump), which times out for n up to 10^5 with a large jump span. The insight is that we don't care which predecessor is reachable — only whether at least one is. That turns it into a counting question. So we use a sliding window with a running count: keep a variable pre equal to the number of reachable indices inside the predecessor window [i-maxJump, i-minJump]. As i advances by one, the window's right edge gains dp[i-minJump] (add it to pre) and its left edge loses dp[i-maxJump-1] (subtract it). Each step is O(1), so the whole pass is O(n). For each i, if s[i]=='0' and pre>0, mark dp[i]=true. The answer is dp[n-1].

逐步走查 / Walkthrough

範例 / Example: s = "011010", minJump = 2, maxJump = 3, n = 6。先確認 s[5]=='0'（末端必須是 '0'，否則永遠不可達）。初始 dp[0]=true，pre=0。

對下標 i：先在 i >= minJump 時把 dp[i-minJump] 加入 pre；再在 i > maxJump 時把 dp[i-maxJump-1] 移出 pre；最後若 s[i]=='0' 且 pre>0 則 dp[i]=true。

i	s[i]	加入 add dp[i-2]	移出 remove dp[i-4]	pre	dp[i]
1	'1'	i<2，不加 / skip	i≤3，不移 / skip	0	false
2	'1'	+dp[0]=true → +1	skip	1	false（s[2]='1'）
3	'0'	+dp[1]=false	skip	1	true（pre>0）
4	'1'	+dp[2]=false	−dp[0]=true → −1	0	false
5	'0'	+dp[3]=true → +1	−dp[1]=false	1	true（pre>0）

dp[5]=true，回傳 true。對照題目：路徑 0 → 3 → 5 確實可行。 / dp[5]=true, return true, matching the path 0 → 3 → 5.

Solution — C

// 演算法 / Algorithm: dp[i] = 下標 i 是否可達。用滑動視窗 + 前綴計數 pre 記錄
// 前驅區間 [i-maxJump, i-minJump] 內有多少可達位置，整段掃描只需 O(n)。
// dp[i] = is index i reachable. A sliding-window running count `pre` tracks how
// many reachable predecessors lie in [i-maxJump, i-minJump]; one O(n) pass.
#include <string.h>   // strlen
#include <stdlib.h>   // calloc / free
#include <stdbool.h>  // bool, true, false

bool canReach(char* s, int minJump, int maxJump) {
    int n = strlen(s);                 // 字串長度 / length of the string
    if (s[n - 1] == '1') return false; // 末端是 '1' 就永遠落不上去 / last cell '1' is unreachable

    // calloc 配置 n 個 bool 並全部清為 0(false) / allocate n bools, all zero(false)
    bool* dp = (bool*)calloc(n, sizeof(bool));
    dp[0] = true;                      // 起點一定可達 / the start is always reachable
    int pre = 0;                       // 視窗內可達前驅的個數 / count of reachable predecessors in window

    for (int i = 1; i < n; i++) {      // 從 1 開始逐一判斷每個下標 / decide each index from 1 onward
        // 視窗右端新進來的元素是 dp[i-minJump]；i>=minJump 時它才存在
        // The element entering the window's right edge is dp[i-minJump]; valid when i>=minJump
        if (i >= minJump && dp[i - minJump]) pre += 1;

        // 視窗左端滑出的元素是 dp[i-maxJump-1]；i>maxJump 時它才曾在視窗內
        // The element leaving the window's left edge is dp[i-maxJump-1]; valid when i>maxJump
        if (i > maxJump && dp[i - maxJump - 1]) pre -= 1;

        // 當前格是 '0' 且視窗裡至少有一個可達前驅，則本格可達
        // Current cell is '0' and at least one reachable predecessor exists → reachable
        if (s[i] == '0' && pre > 0) dp[i] = true;
    }

    bool ans = dp[n - 1];              // 答案就是能否到達最後一格 / answer = is the last cell reachable
    free(dp);                          // 釋放動態記憶體，避免洩漏 / free heap memory to avoid a leak
    return ans;
}

Solution — C++

// 演算法 / Algorithm: 與 C 版相同。dp[i] 表示可達；用滑動視窗計數 pre 維護
// 前驅區間 [i-maxJump, i-minJump] 內的可達數量，單趟 O(n) 掃描。
// Same as the C version. dp[i] = reachable; a sliding-window count `pre` keeps
// the number of reachable predecessors in [i-maxJump, i-minJump] in one O(n) pass.
#include <string>
#include <vector>
using namespace std;

class Solution {
public:
    bool canReach(string s, int minJump, int maxJump) {
        int n = s.size();                    // 字串長度 / length of the string
        if (s[n - 1] == '1') return false;   // 末端非 '0' 直接不可達 / last cell must be '0'

        // vector<bool> 是可變長陣列；這裡長度 n，全部初始化為 false
        // vector<bool> is a resizable array; size n, every element starts false
        vector<bool> dp(n, false);
        dp[0] = true;                        // 起點可達 / the start is reachable
        int pre = 0;                         // 視窗內可達前驅個數 / reachable predecessors in window

        for (int i = 1; i < n; ++i) {        // 逐一判斷每個下標 / evaluate each index
            // 右端新增 dp[i-minJump] / right edge gains dp[i-minJump]
            if (i >= minJump && dp[i - minJump]) ++pre;
            // 左端移除 dp[i-maxJump-1] / left edge drops dp[i-maxJump-1]
            if (i > maxJump && dp[i - maxJump - 1]) --pre;
            // 落點為 '0' 且視窗內有可達前驅 → 本格可達
            // Landing cell is '0' and window has a reachable predecessor → reachable
            if (s[i] == '0' && pre > 0) dp[i] = true;
        }

        return dp[n - 1];                    // 回傳末端是否可達 / return whether the last cell is reachable
    }
};

複雜度 / Complexity

Time: O(n) — n 是字串長度。我們只用一個 for 迴圈從頭掃到尾，每一步的視窗加減、判斷都是常數時間 O(1)，沒有巢狀掃描，所以總和是線性。 / n is the string length. A single pass with O(1) work per step (the window add/remove and the check) — no nested scan — so the total is linear.
Space: O(n) — 需要一個長度 n 的 dp 陣列記錄每個下標是否可達；pre 只佔常數空間。 / We need a dp array of length n to record reachability per index; pre uses only constant extra space.

Pitfalls & Edge Cases

末端是 '1' / Last cell is '1'：若 s[n-1]=='1'，無論如何都跳不上去，必須回傳 false。程式開頭直接特判，也避免後面誤判。 / If the last cell is '1', it can never be landed on; we special-case it up front so the final answer is correct.
視窗邊界 off-by-one / Window boundary off-by-one：新進元素是 dp[i-minJump]（條件 i>=minJump），滑出元素是 dp[i-maxJump-1]（條件 i>maxJump，注意是嚴格大於）。少了 -1 或把 > 寫成 >= 都會數錯視窗範圍。 / The entering element is dp[i-minJump] (need i>=minJump) and the leaving one is dp[i-maxJump-1] (need i>maxJump, strict). Dropping the -1 or using >= miscounts the window.
下標越界 / Index out of bounds：上面的 i>=minJump 和 i>maxJump 條件正是用來保證 i-minJump 與 i-maxJump-1 不會變成負數而越界存取。 / Those two guards ensure i-minJump and i-maxJump-1 never go negative and read out of bounds.
只看「是否存在」而非「哪一個」/ Existence, not identity：pre>0 表示視窗裡至少有一個可達前驅就夠了；不需要知道具體位置，這正是能把 O(n·maxJump) 降到 O(n) 的關鍵。 / Checking pre>0 (at least one reachable predecessor) is all we need — knowing exactly which one is unnecessary, and that is what reduces O(n·maxJump) to O(n).
記憶體釋放 (C) / Free memory (C)：C 版用 calloc 配置 dp，回傳前務必 free，否則造成記憶體洩漏。 / The C version allocates dp with calloc; remember to free it before returning to avoid a memory leak.