前缀和优化 DP

当 DP 转移方程是如下形式的时候

image

计算 dp[i] 时需要一步求和 sum(dp[a..b])，如果用遍历的方式，则转移的时间复杂度为 O(N)。

如果在状态转移的过程中维护一个 dp 数组的前缀和 sums，则这步求和可以用 sums[b + 1] - sums[a] 直接得到，转移的时间复杂度变为 O(1)

题目

1871. 跳跃游戏 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 <= 1e5
s[i] 要么是 '0' ，要么是 '1'
s[0] == '0'
1 <= minJump <= maxJump < s.length

算法1: 基础单串DP

状态定义
dp[i] := 从 0 能否到达 i, 1 为能到达，0 为不能到达

初始化
若 dp[0] == 1 

答案:
dp[n - 1]

状态转移
dp[i] = 1 dp[j] 中存在 1
      = 0 dp[j] 中不存在 1 或 i - minJump < 0
其中 j 属于 [min(i - maxJump, 0), i - minJump]

代码(C++)

注: O(N^2) 超时

class Solution {
public:
    bool canReach(string s, int minJump, int maxJump) {
        int n = s.size();
        vector<int>dp(n, 0);
        dp[0] = 1;
        for(int i = 1; i < n; ++i)
        {
            if(s[i] == '1' || i - minJump < 0)
                continue;
            for(int j = max(0, i - maxJump); j <= i - minJump; ++j)
                if(dp[j] == 1)
                {
                    dp[i] = 1;
                    break;
                }
        }
        return dp[n - 1];
    }
};

算法2: 前缀和优化 DP

在状态转移时，要问 [max(i - maxJump, 0), i - minJump] 这个区间内中有无 dp[j] 的值为 1，

如果用遍历的方式，需要 O(N) 转移。可以用前缀和的方式，将查询改为问 dp[max(i - maxJump, 0) .. i - minJump] 中是否有 1，也就是 sum(dp[max(i - maxJump, 0) .. i - minJump]) 是否大于 0。

如果状态转移时维护一个 dp 数组的前缀和 sums，那么这步查询就可以 O(1) 完成，也就是 sums[i - minJump + 1] - sums[max(i - maxJump, 0)]

代码(C++)

class Solution {
public:
    bool canReach(string s, int minJump, int maxJump) {
        int n = s.size();
        vector<int> dp(n);
        dp[0] = 1;
        vector<int> sums(n + 1);
        sums[1] = 1;
        for(int i = 1; i < n; ++i)
        {
            if(s[i] == '0' && (i - minJump >= 0))
                if(sums[i - minJump + 1] - sums[max(i - maxJump, 0)] > 0)
                    dp[i] = 1;
            sums[i + 1] = sums[i] + dp[i];
        }
        return dp[n - 1];
    }
};