MediumRating 1896
1871. Jump Game VII
stringdynamic-programmingsliding-windowprefix-sum
解題說明
Jump Game VII
題目描述：
給定一個二進位字串 s（由 '0' 和 '1' 組成），以及整數 minJump 和 maxJump。起始位置為索引 0，只能跳到值為 '0' 的位置，每次跳躍距離在 [minJump, maxJump] 之間。判斷能否到達最後一個位置。
解題思路： 使用 DP + 前綴和（或滑動窗口差分技巧）。
dp[i]= 是否能到達位置 i。初始dp[0] = true。- 位置 i 可達的條件：
s[i] == '0'且存在某個 j 滿足i - maxJump <= j <= i - minJump使得dp[j] = true。 - 直接檢查範圍內是否有 true 需要 O(maxJump) 時間。用前綴和優化：維護
pre[i]=dp[0] + dp[1] + ... + dp[i]，則範圍內的可達位置數 =pre[i-minJump] - pre[i-maxJump-1]，若大於 0 則 i 可達。 - 時間複雜度降為 O(n)。
C++ 解法
複雜度分析
時間複雜度：O(n) — 一次遍歷，每個位置做常數操作。
空間複雜度：O(n) — DP 陣列。
虛擬碼
1. If s[n-1] == '1', return false 2. Initialize dp[0..n-1] = false, dp[0] = true 3. Initialize reachable = 0 (count of true dp values in sliding window) 4. For i from 1 to n-1: a. If i >= minJump and dp[i - minJump] is true: reachable++ b. If i > maxJump and dp[i - maxJump - 1] is true: reachable-- c. If s[i] == '0' and reachable > 0: dp[i] = true 5. Return dp[n-1]
其他解法
BFS O(n)：從位置 0 開始 BFS，維護一個指標記錄已經嘗試過的最遠位置，避免重複訪問。每個位置最多入隊一次，總時間 O(n)。
前綴和 DP O(n)：用整數前綴和陣列替代滑動窗口計數器，pre[i] = sum(dp[0..i])。dp[i] = (s[i]=='0') && (pre[i-minJump] - pre[max(0, i-maxJump)-1] > 0)。邏輯等價但需要額外的前綴和陣列。
延伸思考
- 如果跳躍有成本（如每跳一步花費 1），要求到達終點的最小成本，如何修改？
- 如果 minJump 和 maxJump 隨位置變化（每個位置有不同的跳躍範圍），如何處理？
- Jump Game 系列（I 到 VII）各自的核心差異是什麼？分別用了什麼演算法？