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)各自的核心差異是什麼?分別用了什麼演算法?