第242场Leetcode周赛 5765.跳跃游戏 VII

传送门

题目描述

给你一个下标从 0 开始的二进制字符串 s 和两个整数 minJump 和 maxJump 。一开始，你在下标 0 处，且该位置的值一定为 ‘0’ 。当同时满足如下条件时，你可以从下标 i 移动到下标 j 处：

i + minJump <= j <= min(i + maxJump, s.length – 1) 且
s[j] ‘0’.
如果你可以到达 s 的下标 s.length – 1 处，请你返回 true ，否则返回 false 。

样例

示例 1：
输入：s = “011010”, minJump = 2, maxJump = 3
输出：true
解释：
第一步，从下标 0 移动到下标 3 。
第二步，从下标 3 移动到下标 5 。

示例 2：
输入：s = “01101110”, minJump = 2, maxJump = 3
输出：false

数据范围

2 <= s.length <= 105
s[i] 要么是 ‘0’ ，要么是 ‘1’
s[0] ‘0’
1 <= minJump <= maxJump < s.length

解题思路

在比赛的过程中写了一发记忆化搜索，疯狂超时，死在了最后两个样例上，不知道为什么会超时，所有位置只可能被访问一次啊，应该也是O(n)的时间复杂度啊？搞不懂。
官方给的解法是动态规划+前缀和优化
dp[i]表示：i这个位置能不能被访问到，然后我们就动态规划的判断他的上一步能不能走到就行了。如何判断上一步能不能走到？因为它的上一步不是一个区间的范围内吗，dp[i]表示i这个位置能不能被访问到，能访问到就是1，不能访问到就是0，因此若它的上一步的那个区间段的和大于0就说明，至少有一个位置可以走到当前的i这里，求区间和我们利用前缀和优化。
最后总的时间复杂度是O(n)。

代码

//dp+前缀和
class Solution {
public:
    bool canReach(string s, int minJump, int maxJump) {
        int len = s.size();
        if(s[len-1] == '1') return false;
        vector<int> dp(len+1), a(len+1);        //a是前缀和数组
        dp[1] = 1;
        a[1] = 1;
        for(int i = 2; i <= len; i ++ )
        {
            if (s[i - 1] != '0' || i <= minJump)
            {
                a[i] = a[i - 1];
            }
            else
            {
                int l = max(1, i - maxJump), r = max(1, i - minJump);
                if (a[r] > a[l - 1]) dp[i] = 1;
                a[i] = a[i - 1] + dp[i];
            }
        }
        return dp[len];
    }
};

记忆化搜索的超时代码

int f[100010];
class Solution {
public:
    int dp(string& s, int minJump, int maxJump,int x)
    {
        if(f[x] != -1) return f[x];
        if(x - minJump < 0)
        {
            f[x] = 0;
            return f[x];
        }
        for(int i = max(0,x - maxJump); i<=x-minJump; i++)
        {
            if(s[i] == '0')
            {
                if(f[x] != -1) f[x] = f[x] | dp(s,minJump,maxJump,i);
                else f[x] = dp(s,minJump,maxJump,i);
            }
            if(f[x] == 1) return 1;
        }
        f[x] = 0;
        return f[x];
    }
    bool canReach(string s, int minJump, int maxJump) {
        memset(f,-1,sizeof f);
        int len = s.size();
        f[0] = 1;
        for(int i = 1; i<len; i++)
        {
            if(s[i] == '1') f[i] = 0;
        }
        return dp(s,minJump,maxJump,len-1);
    }
};