背景

用几个词总结集训感想：难？无聊？无助？ 有点抽象……

好吧，就是难了。其实就是动态规划，有什么难的。但是它讲得太快了，最关键的是它没有 excaildraw ！！！

它讲得不详细，所以我也只能讲粗略一点了。

---

这是基础动态规划（ DP，不要问我全称是什么 ）的三个类型：

1. 线性DP；
2. 背包DP；
3. 区间DP。

其实还有树形 DP 、状压 DP 、轮廓线 DP……不过是提高组的内容。

动态规划——1、线性DP

还好这一块是 D 老师讲的。 线性DP 。

动态规划——2、背包DP

还好这一部分先学了一点。背包 DP 经常是这样类型的题目：有一个背包容量为 $V$ ， $N$ 件物品，给出每件物品的重量 $C_i$ 和价值 $W_i$ ，求背包最多能装下价值为多少的物品。不过背包 DP 也有分类：

1. 01背包
2. 完全背包
3. 混合背包

背包——01背包

每件物品只能选择 $0$ 或 $1$ 件，这是 01背包。还是用 D 老师的 DP 步骤来做吧。

一、分析

这……都叫 DP 了，能不用 DP 吗？ 这是 DP 学的公理。

二、定义状态变量

可以定义一个二维的 DP 数组。 dp[i][j] 表示前 i 个物品， 背包最大能装 j 时的最大价值。

三、状态转移方程

怎么转移呢？遍历每一个物品和重量。对于每一个物品，都有选和不选连个选择。但是选的前提是背包可以装得下当前物品。如果选择当前物品，那么 dp[i][j] 就是前 $i-1$ 个物品、当前重量减去当前物品的重量（即 $j-C_i$ ）的价值加上当前物品的价值。如果不选当前物品，那么价值还是前 $i-1$ 个物品、当前重量的最大价值。下面是状态转移方程：

$$dp[i][j] = \begin{cases} 选 & dp[i-1][j-w[i]] \\ 不选 & dp[i-1][j] \end{cases} $$

取较大值。

四、初始状态和边界

因为要求最大值，所以全部初始化为 $0$ 就好了。

五、答案

就是 dp[n][v] ，即前 $N$ 项物品、背包容量为 $V$ 时的最大价值。

例题： 简单背包问题 。

背包——完全背包

在讲完全背包之前，先讲一下 01 背包的空间优化（其实是我不知道完全背包的二维写法）。

通过观察，我们可以发现，这个二维的数组其实可以优化为一维（别问我为什么，因为我也不知道）。这一 “前 $i$ 个物品”没有什么用，所以可以把数组改为：背包容量为 $j$ 时的最大价值。但是这导致一个问题。例如这样一组数据：

10 3
1 1
2 2
3 3

很明显，即使把所有物品都装入背包，也只有 $9$ 的价值。但是把数组改为一维时，却输出了 $10$ 。这就是一个问题：物品会重复选择。因为选择当前物品时，会关系到当前物品之前的物品，所以会重复。但是如果把循环倒序，只会关系到当前物品之前的物品，所以不会有问题。下面进入完全背包。

每件物品都能重复选择，这就是完全背包。这就联想到上面的问题：物品会重复选择。所以只要把遍历重量的循环正序，就是完全背包。

例题： 完全背包问题 。

背包——多重背包

就是 01 背包和完全背包的结合体。它通常会给你一个 $num$ 存储每一个物品的数量。这只需要增加一个循环来遍历物品选择的数量就差不多了。

下面是背包 DP 的核心代码：

for (int i = 1; i <= n; i++)
{
	for (int j = 1; j <= v; j++) // for (int j = v; j >= 1; j--)
	{
		if (j >= c[i])
		{
			//for (int k = 1; k <= num[i]; k++)
			dp[j] = max(dp[j], dp[j - c[i]] + w[i]);
			//dp[j] = max(dp[j], dp[j - c[i] * k] + w[i] * k);
		}
	}
}

动态规划——区间 DP

这太惨了，一点了解都没有。

这是我对区间 DP 的一些见解：类似分治，将区间分为两半，就是模拟断点。先给模板吧，因为区间 DP 没什么标准题目。

for (int len = 2; len <= n; len++)
{
	for (int s = 1; s <= n - len + 1; s++)
	{
		int e = s + len - 1;
		for (int k = s; k < e; k++)
		{
			dp[s][e] = min(dp[s][e], dp[s][k] + dp[k + 1][e]);
		}
	}
}

区间 DP 的题目的数组也是二维，表示区间 $[i,j]$ 的答案。

例题： 合并石子 。

一、分析问题

和上面一样。

二、定义状态变量

定义 dp[i][j] 表示区间 $[i,j]$ 的最小得分。

三、状态转移方程

一段区间的得分就是这段区间所有数字的和，这可以用前缀和来优化。根据上面的，这一段区间可以分为 dp[s][k] 和 dp[k + 1][e] ，要记得加上得分。

四、初始状态和边界

因为要求最小值，所以要初始化为极大值。

五、答案

区间 $[1,n]$ 的答案就是了。