前缀和优化DP

  |  

摘要: 本文介绍了动态规划的一种优化方法:前缀和优化 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