前缀DP

例一、前缀和

给定⼀个数组 a ，求出所有起点到当前位置的和

f[i] = f[i-1] + a

例二、前缀最大值

f[i] = max(f[i-1], a)

例三、爬楼梯

假设你正在爬楼梯。需要 n 阶你才能到达楼顶。每次你可以爬 1 或 2 个台阶。有多少种不同的⽅法爬到楼顶呢？

状态：f[i]表示从起点到阶梯i有多少种方式

状态转移：f[i] = f[i - 1] + f[i - 2]

拓展：每次向上一步或者向下直接跳到楼底，问k次行动后，到达第x阶台阶的方案数（以行动次数找状态）

例四、最大子数组和

给一个整数数组nums，找出一个最有最大和的连续子数组（子数组最少包含一个元素），返回其最大值

状态：f[i]表示以当前节点i结尾的子数组的最大值

则f[i] = max(f[i] + ai)

以问题做状态、以i开头、以i结尾作为状态定义

例五、过河卒

类似二维dp或者双重前缀dp吧

例六、滚动数组

利用奇偶性，把i % 2这个数组当作当前阶段,1 - i % 2当作上一阶段

1
2
3
4
5
6
7
8
9
10
11
12
vector<vector<int>> dp(2, vector<int>(m + 1));
for(int i = 0; i <=n; i ++){
    auto &cur = dp[i % 2], &pre = dp[1 - i % 2];
    auto &cur = dp[i & 1], &pre = dp[~i & 1]
    for(int j = 0; j <= m; j ++){
        if(blocked[i][j]) cur[j] = 0;
        else if(i == 0 && j == 0) cur[j] = 1;
        else if(i == 0) cur[j] = cur[j - 1];
        else if(j == 0) cur[j] = pre[j];
        else cur[j] = pre[j] + cur[j - 1];
    }
}

例七、有奖问答

一共答n题，每答对一次分数加1，答错分数清0，可以随时停止作答，问有多少种方案最终可以拿到k分

状态：f[i][j]表示答了i题，分数为j的方案数

例八、打家劫舍

你是⼀个专业的小偷，计划偷窃沿街的房屋。每间房内都藏有⼀定的现金，影响你偷窃的唯一制约因素就是相邻的房屋装有相互连通的防盗系统，如果两间相邻的房屋在同⼀晚上被小偷闯⼊，系统会自动报警。给定⼀个代表每个房屋存放金额的⾮负整数数组，计算你不触动警报装置的情况下，⼀夜之内能够偷窃到的最⾼金额。

状态：f[i][-], i表示偷到第几家，-为0、1，表示是否偷了这一家，f[i][j]为当前最大偷窃金额

状态转移：f[i-1][0] -> f[i][0] || f[i][1] f[i-1][1] -> f[i][0]

1
2
3
4
5
6
7
8
int n = nums.size();
auto dp = vector(n, vector(2, 0));
dp[0][1] = nums[0];
for (int i = 1; i < n; i ++) {
	dp[i][0] = max(dp[i - 1][0], dp[i - 1][1]);
	dp[i][1] = dp[i - 1][0] + nums[i];
}
return max(dp[n-1][0], dp[n-1][1]);

例九、打家劫舍（二）

上题的衍生，房屋围成一圈

状态：f[i][robber][first],first额外记录第一个节点有没有偷窃，用于判断最后的合法状态

1
2
3
4
5
6
7
8
9
10
if (n == 1) return nums[0];
auto dp = vector(n, vector(2, vector(2, 0)));
dp[0][1][1] = nums[0];
for (int i = 1; i < n; i ++) {
	for (int first = 0; first < 2; first ++) {
		dp[i][0][first] = max(dp[i-1][0][first], dp[i-1][1][first]);
		dp[i][1][first] = dp[i-1][0][first] + nums[i];	
	}
}
return max({dp[n-1][1][0], dp[n-1][0][0], dp[n-1][0][1]});

01DP

这类问题一般都是在一维度数组中依次选取前后坐标无关的x个值，且可以将历史的最优值或方案浓缩为有限的状态，以在限定条件下达到最优值，或统计在限制条件合法的方案数

例一、最高乘法得分

给你⼀个⼤⼩为4的整数数组 a 和⼀个⼤⼩⾄少为4的整数数组b
从数组里选择4个下标并与a按顺序相乘得到得分，求出最大得分
示例：输⼊：a=[3,2,5,6],b=[2,-6,4,-5,-3,2,-7] 输出：26
解释： 选择下标0,1,2和5。得分为 3 2 + 2 (-6) + 5 4 + 6 2 = 26

分析：以f[i][k]表示前i个数选择了k个下标时所达到的最大值
则选择或没有选择第i个数字作为下标
状态转移方程：f[i][k] = max(f[i-1][k], f[i-1][k-1] + a[k-1][i-1]) 注意坐标偏移

==深度思考==
i位置所有的状态，都是从i-1继承过来的，因为选取的数字坐标⽆关，不需要关⼼上⼀个选 取的数字在哪，只需要关注历史上最优的状态是什么，因此，我们可以将状态分为当前状态和历史状态

  • 先将当前状态从历史状态继承过来（相当于批 量处理了绿⾊部分）
  • 再看这次选择会对当前状态造成什么改变，去最优值或统计⽅案
  • 将当前状态变成历史状态（因为对后续的决策来说，【当前】已经成为了【历史】）

得到新的状态转移方程cur[k] = max(cur[k], his[k-1] + b * a_k-1)

优势

  • 不需要关注枚举值的下标（很多题目数组的坐标和DP状态有+1, -1的便宜，容易弄错)
  • 代码干净简洁，一些边界情况不需要额外处理
  • 省内存
1
2
3
4
5
6
7
8
9
10
vector his(5, -1e11), cur; 
his[0] = 0; 
for (long long x : b) { 
	cur = his; // 从历史继承 
	for (int k = 1; k <= 4; k ++) { 
	cur[k] = max(cur[k], his[k - 1] + a[k - 1] * x); 
	}
	his = cur; // 成为历史
}
return his[4];

例二、最大的和

给一个数组，有正有负，任选一些数字使得和最大
例如 输⼊：arr=[2,-6,4,-5,-3,2,-7] 输出：13
解释：只选正数

DP的思路 his --(+x)--> cur

1
for(auto &x : arr) his = max(his, his + x); // his初始化为0

==深度思考==
是不是只需要his就够了？

  • 要注意计算顺序
  • 如果转移的时候有交叉就不行

例三、最大的乘积

在一个有正有负的数组中任选一些数字组成非空子集使得他们的乘积最大
示例：输⼊：nums=[3,-1,-5,2,5,-9] 输出：1350

分析：由于会出现负负得正的情况，不能单纯选取负数
因此用状态0, 1来表示正数和负数的最大值
或者将0作为最大值；1作为最小值，可以减少对负数的判断

初始化需要选则1为初始条件
状态转移方程
cur[0] = max(cur[k], x, his[k] * x, his[1-k] * x)
cur[1] = min(cur[k], x, his[k] * x, his[1-k] * x)

1
2
3
4
5
6
7
8
9
10
vector<long long> his(2, nums[0]), cur;
for (int i = 1; i < nums.size(); i++) {
  long long x = nums[i];
  cur = his;
  cur[0] = max({cur[0], x, his[0] * x, his[1] * x});
  cur[1] = min({cur[1], x, his[0] * x, his[1] * x});
  his = cur;
}

return his[0];

例四、最大交替子序列和

给你⼀个数组，有正有负，从中选择⼀些数字组成新的数组，新数组的权值等于奇数位的和减偶数位的和，求最⼤的权值
示例：输⼊：nums=[4,2,5,3] 输出：7 解释：最优⼦序列为[4,2,5]，交替和为(4+5)-2=7

状态：选择了奇数次还是偶数次
转移：偶数次+x，奇数次-x；任何数字都可以单独作为第一次选择

cur[0] = max(cur[0], x, his[1] + x)
cur[1] = max(cur[1], his[0] - x)

1
2
3
4
5
6
7
8
vector<long long> his(2, 0), cur;
for (long long x : nums) {
  cur = his;
  cur[0] = max({cur[0], x, his[1] + x});
  cur[1] = max(cur[1], his[0] - x);
  his = cur;
}
return his[0];

例五、不同的子序列

给你两个字符串s和t，统计并返回在s的子序列中t出现的个数，结果需要对10^9+7取模
示例： 输⼊：s=”rabbbit”,t=”rabbit” 输出：3
解释： ==rabb==b==it== ==rab==b==bit== ==ra==b==bbit==

状态：his(k)表示组成到前k个t字母的方案数
转移：字符c等于t[k-1]时才是合法的转移方案
用0表示1个都没匹配，1表示匹配了第0个字符

his(0) = 1
cur(k) = cur(k) + his(k-1), c = t_k-1

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
const int mod = 1e9 + 7;
int n = t.size();
auto his = vector(n + 1, 0);
his[0] = 1;
auto add = [&](int& x, int y) {
  x += y;
  if (x >= mod) x -= mod;
};
for (char c : s) {
  for (int k = n; k > 0; k--) {
    if (c == t[k - 1]) {
      add(his[k], his[k - 1]);
    }
  }
}
return his[n];

例六、股票买卖的最佳时机

给定一个整数数组prices和一个整数k，其中prices[i]是某支给定的股票在第i天的价格
设计一个算法来计算你所能获取的最大利润。最多可以完成k笔交易，即最多可以买k次，卖k次
示例：输⼊：k=2,prices=[3,2,6,5,0,3] 输出：7
解释：在第2天(股票价格=2)的时候买⼊，在第3天(股票价格=6)的时候卖出,这笔交易所能获得利润=6-2=4。 随后，在第5天(股票价格=0)的时候买⼊，在第6天(股票价格=3)的时候卖出,这笔 交易所能获得利润=3-0=3。

分析：就和最大子序列和类似，买是减，卖是加，但是不能只记录奇偶，需要记录具体的第几次
选择2k个数字，一定是买、卖、买交替，买可以看做减少了多少钱，卖可以看做赚了多少钱

状态： his(k)第k次操作的最大值
转移：奇数次减，偶数次加

his(k) = -inf, k > 0; 0, k = 0
cur(k) = max{cur(k), his(k-1) + x}, k % 2 = 0
cur(k) = max{cur(k), his(k-1) - x}, k % 2 = 1

1
2
3
4
5
6
7
8
9
10
11
12
13
int n = prices.size();
auto his = vector(K * 2 + 1, -1000);
his[0] = 0;
for (auto x : prices) {
  for (int k = K * 2; k > 0; k--) {
    if (k & 1) {
      his[k] = max(his[k], his[k - 1] - x);
    } else {
      his[k] = max(his[k], his[k - 1] + x);
    }
  }
}
return *max_element(his.begin(), his.end());

==总结==

  • 位置无关的从数组中选取一个组合
  • 可将历史的最优值浓缩为有限个数的状态
  • 只需要开history和current数组记录历史和当前状态
  • 如果转移不交叉，只需要history数组

有 cur 和 his 两份状态：
更新顺序通常无所谓。
只有一份 his，且原地更新：
dp[k] 依赖 dp[k - 1] → 倒序；
dp[k] 依赖 dp[k + 1] → 正序。

一般线性DP

状态：以某一维度划分阶段，增加维度表示信息
转移：

  • 前缀DP：只和前一阶段有关
  • 01 DP：只和历史阶段有关
  • 一般线性DP：可以从过往所有阶段转移过来

    例题一

文字工作 - 洛谷 B3636 - Virtual Judge

机器猫要在电脑前打字。一共需要打 n 个字，但现在文档里只有一个字。

机器猫有两种操作可以做。假设现在已经有 x 个字，机器猫可以选择：

  • 往文档最后加一个字。字数变成 x+1。
  • 把文档复制粘贴一遍。字数变成 2x。

问机器猫至少需要多少次操作，才能得到恰好 n 个字。

状态：dp[i]表示字数为i需要的最小次数
转移： i & 1: dp[i] = dp[i-1] + 1
~i & 1: dp[i] = min(dp[i-1], dp[i / 2]) + 1

例题二

园艺 - 洛谷 P12175 - Virtual Judge

小蓝从左到右种了 n 棵小树，第 i 棵树的高度为 hi​，相邻树的间隔相同。小蓝想挪走一些树使得剩下的树等间隔分布，且从左到右高度逐渐上升（相邻两棵树高度满足右边的比左边的高），小蓝想知道最多能留下多少棵树。

状态：dp[i]表示前i颗树剩下树的数量
转移：h[i] > h[i - diff], dp[i] = dp[i - diff] + 1; else dp[i] = 1

例题三

打鼹鼠 - 洛谷 P2285 - Virtual Judge

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
#include <bits/stdc++.h>
using namespace std;
int main() {
  ios::sync_with_stdio(false);
  cin.tie(nullptr);
  int n, m;
  cin >> n >> m;
  vector<array<int, 3>> ms(m);
  for (auto& [t, x, y] : ms) 
    cin >> t >> x >> y;
  auto dist = [](int x1, int y1, int x2, int y2) {
    return abs(x1 - x2) + abs(y1 - y2);
  };
  // dp[i]：最后打到第 i 只鼹鼠时的最大数量
  vector<int> dp(m, 1);
  int ans = 0;
  for (int i = 0; i < m; i++) {
    for (int j = 0; j < i; j++) {
      int timeDiff = ms[i][0] - ms[j][0];
      int distance = dist(ms[i][1], ms[i][2], ms[j][1], ms[j][2]);
      if (timeDiff >= distance) 
        dp[i] = max(dp[i], dp[j] + 1);
    }
    ans = max(ans, dp[i]);
  }
  cout << ans << endl;
}

例题四

最长上升子序列 - 洛谷 B3637 - Virtual Judge

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
#include <bits/stdc++.h>
using namespace std;
int main() {
  ios::sync_with_stdio(false);
  cin.tie(nullptr);
  int n;
  cin >> n;
  vector<int> seq(n);
  for(auto& s: seq) cin >> s;
  vector<int> dp(n, 1);
  // dp[i] 表示以第i个数字结尾的最长序列长度
  for(int i = 0; i < n; i ++){
    for(int j = 0; j < i; j ++){
      if(seq[j] < seq[i]) dp[i] = max(dp[j] + 1, dp[i]);
    }
  }
  cout << *max_element(dp.begin(), dp.end()) << endl;
}

==进阶：优化单调线性DP中转移的维度==
单调队列优化 -> 单调性 -> O(1)
斜率优化 -> 斜率方程 -> O(1), O(log n)
四边形不等式 -> 决策单调性 -> O(1), O(log n)
数据结构优化 -> 快速转移 -> O(?)

最长递增子序列

笛卡尔积DP

背包DP

DAG DP

划分DP

87. 扰乱字符串 - 力扣（LeetCode）

二维DP

72. 编辑距离 - 力扣（LeetCode）

10. 正则表达式匹配 - 力扣（LeetCode）

44. 通配符匹配 - 力扣（LeetCode）

全排列DP

P1171 售货员的难题 - 洛谷