跳躍游戲VII（dp）

1.題目描述

??給你一個(gè)下標(biāo)從 0 開始的二進(jìn)制字符串 s 和兩個(gè)整數(shù) minJump 和 maxJump 。一開始，你在下標(biāo) 0 處，且該位置的值一定為 '0' 。當(dāng)同時(shí)滿足如下條件時(shí)，你可以從下標(biāo) i 移動(dòng)到下標(biāo) j 處：

• i + minJump <= j <= min(i + maxJump, s.length - 1) 且 s[j] == '0'.
  ?如果你可以到達(dá) s 的下標(biāo) s.length - 1 處，請你返回 true ，否則返回 false 。
  原題鏈接：https://leetcode-cn.com/problems/jump-game-vii

2.簡析

??這道題的數(shù)據(jù)范圍是 因此這里考慮采用復(fù)雜度的算法，首先考慮dp；首先定義一個(gè)數(shù)組，表示是否能移動(dòng)到當(dāng)前下標(biāo)。而能否移動(dòng)到下標(biāo) 取決于之前的狀態(tài)，當(dāng) 否則其狀態(tài)轉(zhuǎn)移方程如下：

但是針對每個(gè)下標(biāo)點(diǎn) ，都需要遍歷前面 的元素，算法復(fù)雜度仍為 。由于這里是求這個(gè)范圍內(nèi)是否存在1，因此可以采用前綴和進(jìn)行優(yōu)化，在dp過程中同時(shí)記錄前綴和，然后狀態(tài)轉(zhuǎn)移的時(shí)候可以利用前綴和在的時(shí)間復(fù)雜度內(nèi)判斷當(dāng)坐標(biāo)點(diǎn)是否可以由目標(biāo)區(qū)間內(nèi)某點(diǎn)轉(zhuǎn)移而來，最終整個(gè)算法的復(fù)雜度為。

3.代碼示例

bool canReach(string s, int minJump, int maxJump) {
        int n = s.size();
        if(s[n-1] == '1') return false;
        int presum[n+1], f[n];
        memset(presum, 0, sizeof presum);
        memset(f, 0, sizeof f);
        f[0] = presum[1] = 1;
        for(int i=1; i<n; ++i){
            if(s[i] == '0' && i >= minJump){
               f[i] = presum[i+1-minJump] - presum[max(0, i-maxJump)] > 0? 1 : 0;
            }
            presum[i+1] = presum[i] + f[i];
        }
        return f[n-1]>0;
    }