动态规划1

LYB

2025-03-29 16:32:42

发布于：广东

4阅读

0回复

0点赞

什么题可以用dp？

最大值/最小值
方案数
可行性

怎么写DP

状态：dp数组的含义

dp里面存什么？

题目要求什么，dp数组就存什么

i的寄巧：

使用了前i个元素的最佳答案(背包问题)
使用了前i个元素且最后一个使用的元素是第i个元素的最佳答案(最长上升子序列)

想不出转移方程时的寄巧：

加一维

初始条件

如果状态无法通过转移方程得到，需要初始化

转移方程

最后一步 : 如何到达当前dp状态

循环顺序

在计算dp值的时候，需要已经算出所有前置dp值。

答案

题目所求的内容与dp数组的关系

DP模型

背包DP

01背包

$dp_{i, j} :$ 考虑前 $i$ 个物品，且使用了 $j$ 的空间收益最大值

$dp_{i, j} = \max(dp_{i - 1, j}, dp_{i - 1, j - w_i} + v_i)$

完全背包

$dp_{i, j} :$ 考虑前 $i$ 个物品，且使用了 $j$ 的空间收益最大值

$dp_{i, j} = \max(dp_{i - 1, j}, dp_{i, j - w_i} + v_i)$

// 01背包
for (int i = 1; i <= n; i++) {
	for (int j = m; j >= w[i]; j--) {
		dp[j] = max(dp[j], dp[j - w[i]] + v[i]);
	}
}
// 完全背包
for (int i = 1; i <= n; i++) {
	for (int j = w[i]; j <= m; j++) {
		dp[j] = max(dp[j], dp[j - w[i]] + v[i]);
	}
}
// 背包不能不装满
for (int i = 1; i <= m; i++) dp[i] = -INF;

时间复杂度

$O(nm)$

区间DP

将 $[l, r]$ 完全删除、XXX的方案数、合并成一个区间.

状态

$dp_{i, j} : $ 将区间 $[i, j]$ 做XXX操作后可以获得的最大值/方案数。

$i: $ 区间左端点， $j: $ 区间右端点

转移方程

$dp_{i, j} = dp_{i, k} + dp_{k + 1, j} (k \in [i, j - 1])$

循环顺序

先枚举区间长度，通过小区间获得大区间的答案
枚举区间左端点
枚举k （如果需要）

答案

$dp_{1, n}$

时间复杂度

$O(n^3)$

状压DP

状态

$dp_i$ : $i (010011)_2$ 表示选择了第0个、第1个、第4个物品的状态

转移方程

$dp_{010011_2} \leftarrow dp_{010010_2}$

答案

$dp_{111111_2}$

时间、空间复杂度

$O(2^n)$

if (x & (1 << i)) : 可以判断x的第i位是否为1

线性DP

观察数据范围

$O(n) 或 O(n\log n): dp_{i, j} \leftarrow dp_{i - 1, j}$

$O(n^2): dp_i \leftarrow dp_j (j \in [1, i - 1])$

双序列DP

状态

$dp_{i, j}$ 表示考虑第一个序列的前 $i$ 个元素和第二个序列的前 $j$ 个元素时的最大值/最小值/方案数

转移方程

如果在原基础上增加一个字符会发生什么。如果增加第 $i$ 个字符,....

时间复杂度

$O(n^2)$

for (int i = 1; i <= n; i++) {
    for (int j = 1; j <= m; j++) {
        if (s[i] == t[j]) dp[i][j] = dp[i - 1][j - 1] + 1;
        else dp[i][j] = max(dp[i - 1][j], dp[i][j - 1]);
    }
}