嘶，突然想起来，高中的时候其实没有认真学过DP（动态规划）的，记忆化搜索和DP只能说是异曲同工之妙，真正的DP核心在于状态转移方程。

之前遇到DP问题，都是直接恩算，尝试找出二维网格里面的一些关系。今天想了想，是应该从背包DP——这最简单的DP开始，一点一点理解动态规划了。

动态规划是一种通过把原问题分解为更简单的子问题，求解子问题来解决复杂问题的方法

长期更新~人菜瘾大。

什么是背包DP？

背包问题简洁的表述就是

有N个物品，第i个物品的价值为V_i，同时它的重量为W_i，有一个背包能装总重为M的物品，
如何取物品，才能使背包内所有物品的价值最大？

背包DP可以被分为以下几个类型

01背包问题

先讲01背包。
参考题目：P2871 [USACO07DEC]Charm Bracelet S

有N个物品，第i个物品的价值为V_i，同时它的重量为W_i且只能取一次，
有一个背包能装总重为M的物品，如何取物品，才能使背包内所有物品的价值最大？

不难想出，我们可以试试每个物品拿或者不拿，可能的组合非常大，为时间复杂度为O(2_N)。
哪怕如果遇到超过背包装不下的状态而跳过，也是不能接受的复杂度。

先把问题简化一下吧，考虑在三个物品的情况下，背包问题如何解决。

构造一下数据^[1]，假设我们的背包能装总重量4的物品（M=4）。

肉眼观察法，一眼定真，很明显拿取 物品0 和 物品1 是最优的选择。
但是，如何求解呢？

某种程度上我们可以求性价比$P_i=\frac{V_i}{W_i}$，,他完美符合我们上述的数据，可我们很容易就举出一个反例。
假设背包能装总重为10的物品。

如果按性价比贪心（只拿最高性价比的）就不能比拿取物品1和2的拥有更高价值，也就不能用于处理背包问题。某种意义上可以帮助简化搜索的过程，但是搜索不是正解（记忆化搜索除外，但也属于一种DP）。

回到最初的哪个例子，我们把问题再次简化一下，将问题分解为情况更小更简单的子问题。如果我们有能装总重量为M的背包，考虑容量更小的背包，以及更少的物品的情况下呢。

根据上面的假设，我们可以列出这样的一个表格，我们把问题拆分为 只拿前i个物品 和 更小的背包 的情况。

不难理解，如果只拿前1个（包括第1个，后面也是）物品，我们在背包能装得下的情况下（第一行可能不全是物品一的价值），就是最优解。这个子问题，解决。

那么只拿前2个呢？现在我们尝试通过子问题来求解新的问题。
我们可以知道分别在背包为0-4的重量时，只考虑拿物品0的最优解。对于我们的只拿前2个的情况，就是考虑在拿1个的基础上，拿或不拿物品1。
我们假设当前背包容量为M_i，以下为重点。

• 拿取了物品1 ：总价值 = 物品0在背包容量为(M_i减物品1的重量)的价值 + N₁的价值
• 放弃物品1 : 总价值 = 物品0在背包容量为M_i的价值

为什么拿取物品0时，背包容量是原容量减去物品1的重量？
因为拿取物品0时，背包空间就相当于少了物品1的重量，自然要去找子问题的最优解，也就是物品0在此背包容量大小的最大值

假如物品装不下怎么办？
不拿。

选取 拿取与放弃物品1的总价值 中最大的值，我们就可以知道在背包容量为M_i的情况下的最优解。

以背包容量为3的情况举例，物品1价值20，重量3。

• 拿取物品1的总价值 = 物品0在背包容量为0的价值 + 物品1价值 = 20
• 放弃物品1的总价值 = 物品0在背包容量为3的价值 = 15
  所以应拿取物品1，总价值为20

是不是有点思路了？类似数学归纳法，我们可以发现，只拿前3个物品的情况下，也就是只拿前2个物品的情况下，考虑拿或不拿物品2的总价值，谁更高。
在前三个物品且背包容量为4的状态下就是我们需要的解。

接下来我们用符号来解释，刚才我们的表就是DP数组，假设选取i为序号≧i的物品，j就是当前背包的容量。
物品序号从0开始哦。
W_i为序号i的物品重量，V_i为序号i的物品价值。

DP[i][j] = max(DP[i - 1][j], DP[i - 1][j - W_i] + V_i)

不能理解的可以去看看前面通过子问题计算某个状态的最大值。使用了符号来表达而已。

最终得到的结果如下，结果就是右下角的DP[2][5] = 35，即为背包的最大价值。

现在我们可以尝试解上文题目了
参考题目：P2871 [USACO07DEC]Charm Bracelet S

#include "iostream"
#include "cmath"
using namespace std;

int DP[3402][99999] = {0}; // 数组DP
int N = 0, M = 0;		   // 物品数量与背包容量

int N_W[3500] = {0}; // 物品重量
int N_V[3500] = {0}; // 物品价值

int main()
{
	cin >> N >> M; // 读取数据
	for (int i = 0; i < N; i++)
		cin >> N_W[i] >> N_V[i];

	for (int i = 0; i <= M; i++) // 初始化第一个物品的情况
		if (i >= N_W[0])
			DP[0][i] = N_V[0];

	for (int i = 1; i < N; i++) // DP循环
		for (int j = 1; j <= M; j++)
			if (j >= N_W[i])												  // 背包容量要大于物品容量才能拿取
				DP[i][j] = max(DP[i - 1][j], DP[i - 1][j - N_W[i]] + N_V[i]); // 比较拿取与不拿取谁更大
			else
				DP[i][j] = DP[i - 1][j];

	cout << DP[N - 1][M]; // 输出结果
	return 0;
}

__ HOLD SHIT, MLE(Memory Limit Exceed)! 二维数组需要的数据量还是太大了__，导致了内存过大，要AC这个题，我们需要接近2GB的内存容量(逃

优化DP数组

分析代码，可以发现DP数组是导致内存膨胀的主要原因。
还是以刚才的DP数组为例，我们发现，当我们更新i = 2这一列的时候，i = 1以前的数据是完全不需要的。
也就是说，前 i - 2 的物品数据是完全不会被使用到的，这样我们就可以用一维数组存储数据了。

同时我们再对背包容量的循环做些优化，可以得到以下代码。

#include "iostream"
#include "cmath"
using namespace std;

int DP[12882] = {0}; // 数组DP
int N = 0, M = 0;	 // 物品数量与背包容量

int N_W[3500] = {0}; // 物品重量
int N_V[3500] = {0}; // 物品价值

int main()
{
	cin >> N >> M; // 读取数据
	for (int i = 0; i < N; i++)
		cin >> N_W[i] >> N_V[i];

	for (int i = 0; i < N; i++) // DP循环
		for (int j = M; j >= N_W[i]; j--)
			DP[j] = max(DP[j], DP[j - N_W[i]] + N_V[i]);

	cout << DP[M]; // 输出结果

	return 0;
}

注：此时第二个for的遍历顺序必须从大往小，因为在二维DP数组中，我们拿取第i个物品时，DP[i - 1][j]是不会被更新的。
但是在一维数组下，物品i在被拿取后，DP[j]就被立即更新，在后续随着j的更新，max(DP[j], DP[j - N_W[i]] + N_V[i])会取到之前被更新的值，也就可以被重复拿取了。
事实上，调换更新顺序就是完全背包问题的解法

完全背包问题

仔细阅读01背包问题的一维解法，你会发现，交换第二层for的顺序就可以完成了。提供代码如下。
这里就不啰嗦了（其实是不知道怎么在md里面链接自己的段落）。

#include "iostream"
#include "cmath"
using namespace std;

int DP[12882] = {0}; // 数组DP
int N = 0, M = 0;	 // 物品数量与背包容量

int N_W[3500] = {0}; // 物品重量
int N_V[3500] = {0}; // 物品价值

int main()
{
	cin >> N >> M; // 读取数据
	for (int i = 0; i < N; i++)
		cin >> N_W[i] >> N_V[i];

	for (int i = 0; i < N; i++) // DP循环
		for (int j = M; j >= N_W[i]; j--)
			DP[j] = max(DP[j], DP[j - N_W[i]] + N_V[i]);

	cout << DP[M]; // 输出结果

	return 0;
}

在重新理解一次理解DP（有点对不起这个标题

DP(Dynamic programming)，动态规划。（我并不认为它的名字和思想有什么关联）

动态规划是一种通过把原问题分解为更简单的子问题，求解子问题来解决复杂问题的方法

通常我们解题的过程如下：

1. 我们在尝试解决背包问题的时候，最先开始制定了一种可能的规则，把原问题分解为不同的子问题。
2. 尝试寻找从i - 1状态（或者更前的状态），更新到当前i状态的规则与方程。（也叫 动态转移方程 ）
3. 确定状态的 边界（前面的解释中我们提前了一步）
4. 根据动态转移方程，得出最终的答案

一步一步来解释吧。
在第一步中，我们将问题分解的过程中需要考虑__最优子结构__ 和 无后效性 以及 子问题的重叠性。

最优子结构：原问题的最优解所包含的子问题的解也能得到最优解
无后效性：子问题的最优解一旦确定，就不再改变。（即使后面有更大更复杂的问题）
子问题的重叠性: 在使用模拟或者递归求解时，总是会重复的求解某些子问题

如果我们构造的子问题有任一不满足，则很可能不能使用DP思想。

在我们成功构造子问题后，需要查找子问题与原问题的关系规则，也就是 动态转移方程。这个也是DP最难的问题，在下也没用很好的技巧帮助你。
个人解题习惯会展开子问题与原问题的解（类似我们构造二维DP数组），构造部分数据手算答案，再寻找可能的关系与规则。

接下来是 边界，其实就是动态转移中的第一个状态。
一个问题总不能有无限的子问题，至少在求解的时候不能，这就需要我们自己构造合理的数据填入，然后再开始进行动态转移。在背包DP的例子中，我们的边界就是背包容量为0和前一个物品的时候。

最后还是要啰嗦的是，一个问题满足以下条件后，才可能使用DP思想解决，最优子结构 和 无后效性 以及 子问题的重叠性。

终于写完啦，写了5h，希望还能对你有所帮助。如果可以的话还请收藏我的blog哦。