前缀和优化 DP

原理

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

$$\begin{array}{rl}dp[i]=f(\sum _{J=a}^{b}dp[j])& (0\le a\le b<i)\end{array}$$

计算 dp[j] 需要先计算 $sum(dp[a...b])$，如果每次都遍历，每次遍历的时间复杂度为 $O(N)$，总体时间复杂度为 $O(N^2)$。

如果在状态转移过程中维护一个 dp 数组的前缀和数组 sums，则可以以空间换时间，每次遍历的时间复杂度为 $O(1)$，总体时间复杂度为 $O(N)$。

例题

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 。

class Solution {
    public boolean canReach(String s, int minJump, int maxJump) {
        int length = s.length();
        boolean[] dp = new boolean[length];
        int[] pre = new int[length + 1];
        dp[0] = true;
        for (int i = 1; i < minJump + 1; i++) {
            pre[i] = 1;
        }
        for (int i = minJump; i < length; i++) {
            int left = i - maxJump;
            int right = i - minJump;
            if (s.charAt(i) == '0' && pre[right + 1] - (left >= 0 ? pre[left] : 0) > 0) {
                dp[i] = true;
                pre[i + 1] = pre[i] + 1;
            } else {
                pre[i + 1] = pre[i];
            }
        }
        return dp[length - 1];
    }
}