算法动态规划

前缀和优化DP

字数统计: 813字   |   阅读时长: 3分
, ,

摘要: 本文介绍了动态规划的一种优化方法：前缀和优化 DP。并拆解了力扣第 1871 题。

【对算法，数学，计算机感兴趣的同学，欢迎关注我哈，阅读更多原创文章】
我的网站：潮汐朝夕的生活实验室
我的公众号：算法题刷刷
我的知乎：潮汐朝夕
我的github：FennelDumplings
我的leetcode：FennelDumplings

前缀和优化 DP

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

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

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

题目

给你一个下标从 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
2
3
4
2 <= s.length <= 1e5
s[i] 要么是 '0' ，要么是 '1'
s[0] == '0'
1 <= minJump <= maxJump < s.length

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

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

算法1: 基础单串DP

1
2
3
4
5
6
7
8
9
10
11
12
13
状态定义
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) 超时

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
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++)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
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];
    }
};
Share