动态规划
前置知识：搜索、贪心、递归以及递推。
在同学们学习动态规划之前，请同学们先掌握基础的搜索以及递归和递推，这对我们学习动态规划有着很好的作用。注意学习动态规划与贪心的区别，所以需要同学们熟悉简单贪心算法。
引入：
相信在还没有学习动态规划之前，很多同学已经听说过关于动态规划的传说甚至有的同学还做过一些动态规划的题目，但是都未真正见过动态规划的真面目。动态规划一直都是算法比赛中最常用的思想，也是算法比赛中的重中之重，同时他也是一类非常难的问题。因此现阶段我们只需要初步了解动态规划即可，随着我们的课程深入，我们还会接触到各式各样的动态规划，所以同学们在学习本章内容的时候不必他太过担心。
小学阶段的动态规划题目都是一些非常简单的题目，但是我们需要学习遇到这类题目的时候我们为什么考虑选择用动态规划而不用其他的算法呢？希望同学们怀着这个问题去学习本章内容。
本阶段我们只学习动态规划中两个最简单的问题，他们是背包问题以及线性动态规划问题。
我们已经接触过很多"求最佳方案"的题目了。遇到这种问题，可以考虑使用贪心算法在每一步决策的时候使用单步最佳方案，或者使用枚举(搜索)算法枚举所有可能的决策。使用贪心算法的问题是"目光短浅"，不一定可以站在全局的角度来统筹决策，可能会出现结果并不是全局最佳的；而使用枚举搜索算法，虽然可以遍历所有的可能，但是如果数据量稍大，就可能会超时。这个时候可以考虑使用动态规划解决这些问题。
动态规划核心是"状态缓存"，将一个状态的统计结果传递到另外一个状态，这有一点类似递推算法。动态规划是算法竞赛的常客，非常考研同学们问题分析和代码实现能力。
什么是动态规划：
例1：纸币问题
某国有\(n(n \leq 1000)\)种纸币，每种纸币面额为正整数\(a_i\)并且有无限张，试问使用至少多少张纸币可以凑出\(w(w \leq 10000)\)的金额。
例如，提供面额\(1、5、10、20、50、100\)元的面额的纸币，要凑足\(15\)元，至少需要\(2\)张(\(1张5元和1张10元\))；提供\(1、5、11\)元的纸币，要凑足\(15\)元，则至少需要\(3\)张(\(3张5元\))。
分析：第一个样例代表了生活中纸币的面额。按照经验，找钱时尽量先用大面额，超过了再用较小面额的，以此类推。对于第一个样例应用上述贪心思路，得到\(15=10+5\)，两种纸币恰好是最优解。然而这个贪心策略对于第二个例子就行不通了。按照贪心策略我们会得到\(15=11+1+1+1+1\)，使用了\(5\)张纸币。但是最优策略却不是，贪心做法先入僵局。
贪心策略的最大问题在于鼠目寸光：它过分关注了最大面额，全程没有给\(5\)任何机会，那么在正式思考这个问题之前，不妨先来看看如何使用搜索结果第二个样例：
#include <bits/stdc++.h>
using namespace std;
int dfs(int w){
if(w == 0){
return 0;
}
if(w < 0){
return INT_MAX;
}
return min(dfs(w - 1), min(dfs(w - 5), dfs(w - 11))) + 1;
}
int main(){
cout << dfs(15);
return 0;
}
令dfs(w)的返回值为凑够\(w\)元最少需要的纸币数。在每个阶段，分别尝试使用一张\(1\)元纸币、一张\(5\)元纸币、一张\(11\)元纸币，分别对剩下的金额继续搜索，即dfs(w - 1)、dfs(w - 5)和dfs(w - 11)。在这三种情况下，我们找到需要纸币总张数最小的情况，加\(1\)返回即可(因为每次尝试都是尝试使用一张)。
思考为什么\(w < 0\) 返回一个无穷大的值。因为\(w < 0\)是不合法的，我们直接让他返回一个很大的值就可以使用min函数判断掉了，即永远不会选到正无穷这个值。
这段程序又短又好写，但是它的效率好低，因为产生了重复计算。考虑一个问题dfs(w)的值对于同一个\(w\)来说，是不是固定的呢？显然，对于凑过\(10\)元钱的最少纸币数只与纸币的面额有关，不会因为调用dfs(10)的先后顺序而改变。换句话说，dfs(w)的返回值是恒定不变的。调用同一个\(w\)它的dfs(w)值一定相同。所以我们可以看出dfs(w)的作用更像是数组。
我们在仔细看递归的过程，实际上发现我们一直都是从当前的\(w\)一直向下递归到\(0\)，对于上面的例子，我们可以看出dfs(w)的时候只考虑和dfs(w - 1), dfs(w - 5), dfs(w - 11)有关。
这是否给了我们启示？如果我们将dfs(w)看成数组dp[w]，可以得出：
dfs(w) = min(dfs(w - 1), dfs(w - 5), dfs(w - 11)) + 1 即三个最小的 + 1即可
等价于：
dp[w] = min(dp[w - 1], dp[w - 5], dp[w - 11]) + 1
所以我们发现，由于每次需要知道更小的值，那我们可以考虑从\(1 - 15\)开始，把每一步的dp[w]算出来即可。
并且由于\(dfs\)的特性，我们会一直优先搜索\(w-1\)，然后搜索\(w-5\)最后搜索\(w-11\)，等价于我们对于同一种金额开始\(for\)循环,设a[j] 为可以选择的金额(\(1、5、11\))，从\(1\)循环到\(15\)为止（表示一直选择该金额，对应dfs(w-a[j])），即 dp[w] = dp[w - a[j]]。
#include <bits/stdc++.h>
using namespace std;
int dp[20]; // dp[i]表示凑够 i 的金额最少需要多少纸币
int main(){
int a[4] = {0, 1, 5, 11};
memset(dp, 127, sizeof dp); // 因为我们要取最小值，赋值无穷大即可
dp[0] = 0; // 凑够 0 的金额不需要纸币 或者说需要 0张纸币
for(int i = 1; i <= 15; i ++ ){ // 计算dp[i] 最小是1 最大是 15 因为dp[15]表示凑够15的金额
for(int j = 1; j <= 4; j ++ ){ // 看一下我当前在用哪一种纸币 找到最小的dp[i - a[j]] + 1
if(a[j] <= i){ // 如果 i 要是 比 a[j] 小 说明会减成负数，是不合法的 不用考虑
//理解dp数组含义，dp[i] 表示凑了 i 金额的最小面额，凑够当前的i元可能从 i - 1 i - 5 i - 11来
// 距离 dp[15] = dp[10] + 1 dp[10] = dp[15 - 5] 为什么减5？因为我们当前选择a[j]是5 考虑放一张5元可不可以
// 15元可能是从10元的基础上加了1张5元来的
// 这里的a[j] 就是 1、5、11 面额的纸币
// 注意要和自己比较一下，因为dp[15]可能是dp[11 + 1 + 1 + 1 +1]也可能是dp[10 + 5]来的
//要看看是已经算过的小还是新来的小 因为我们面额也是从小开始枚举，可能会先算了dp[1 + 1 + 1....+ 1]的情况
dp[i] = min(dp[i], dp[i - a[j]] + 1);
}
}
}
cout << dp[15]; // 表示凑够15元最小数量
return 0;
}
dp[0] = 0其实就是边界，这里采用了\(dp_w\)表示凑够\(w\)的金额最少需要多少张纸币，取代了几乎意义相同的dfs(w)。在计算dfs(w)的时候，我们枚举了当前阶段用了哪张纸币，继续搜索，然后选择答案最优的那个。这里同理，在计算\(dp_w\)的时候也是枚举了这个阶段用了哪张纸币，只不过使用的是之前的答案计算了\(dp_w\)，最终得到目标答案。
分析完上面思路，请同学们好好参考注释理解，并且考虑如果现在让同学们手动输入\(n\)张面额和求出\(w\)金额的最少纸币数量应该怎么写呢？
这样通过把原问题分解成若干相关子问题，在利用已知的答案依次计算未知问题的答案，最终得到原问题答案的方式，称之为动态规划（Dynamic Programming，简称DP）。
动态规划适用基本条件：
一：具有相同子问题
- 首先，我们必须要保证这个问题能够分解出几个子问题，并且能够通过这些子问题来解决这个问题。并且这些子问题也能被分解成相同的子问题进行求解。例如上方例子：我们可以通过
dp[w - 1] dp[w - 5] dp[w - 11]最后得到dp[w],同样队伍dp[w - 1]来说也可以通过dp[w - 1 - 1] dp[w - 1 - 5] dp[w - 1 - 11]得到。 - 也就是说，假设我们一个问题被分解成了\(A、B、C\)三个部分，那么这个\(A、B、C\)三个部分也可以被分解成\(A'、B'、C'\)三个部分，而不能是\(D、E、F\)三个部分。
二：满足最优子结构
- 问题的最优解包含着它的子问题的最优解。即不管前面的策略如何，此后的决策必须是基于当前状态(由上一次决策产生)的最优决策。例如：
dp[w]是由dp[w - 1] dp[w - 5] dp[w - 11]中最优解来的，那么dp[w]也应该是最优解。
三：满足无后效性
"过去的步骤只能通过当前状态影响未来发展，当前状态是历史的总结"。这条特征说明了动态规划只适用于解决当前决策与过去状态无关的问题。状态，出现在策略的任何位置，它的地位相同，都可以实施同样的策略，这就是无后效性的内涵。举例：当我们求出
dp[5]的时候，后面的dp[10]等都可以通过同样的策略来解决，而不会因为dp[5]的出现，使用了不一样的策略.反过来，现在状态应该与前面状态无关，试想一下，如果第\(i\)个状态的改变改变了前面的第\(j\)个状态，是不是转移到第\(j\)个状态的所有状态都会被改变，这样就不满足无后效性。
这是动态规划中极为重要的一点，如果当前问题的具体决策，会对解决其他未来的问题产生影响，如果产生了影响就无法保证决策最优性。
做动态规划的一般步骤
- First，结合原问题和子问题确定状态
- 题目在求什么？要求出这个值我们需要知道什么？什么是影响答案的因素？
- 状态参数一般有：描述位置、描述数量、描述最大最小等。
- Second，确定转移方程
- 初始化边界是什么
- 注意无后效性。
- 根据状态最后一次决策就可以推出状态转移方程。
背包问题选讲
01背包
先来看一个简单的例题：01背包问题I
如果你是一个探险家，有一天跑到了一个地底洞穴，里面有很多很多的金块，当然都是金块了那肯定是不可以拆分的，你现在只有一个承重为\(M(0 \leq M \leq 200)\)的背包，现在探险家发现了有\(N(1\leq N \leq 30)\)种金块，每一个金块的重量分别为\(w_1, w_2, ....,w_n\),价值为\(v_1,v_2,....,v_n\)，而且每一种金块有且只有一个，求我们可以带回去的最大价值。
假设我们发现了\(4\)种金块，每一种金块的价值(\(v\))和重量(\(w\))如下图；其中\(capacity\)表示我的背包容量，\(n\)表示一共有几种金块。
重新思考一个问题，为什么我们把他叫做\(0/1\)背包呢？
答案很简单，因为我们发现每种只有\(1\)个，对于每一种金块，我们有哪几种选择呢？很显然答案只有两个，拿还是不拿，如果拿我们记为\(1\)，不拿我们记为\(0\)，这是不是是\(0/1\)背包的含义呢。
这个问题怎么做？同学们可以先自行思考，然后在阅读以下内容。
根据前面的纸币问题，我们可以考虑dfs，对于每一个物品我们选还是不选来进行dfs。我们可以的到如下的搜索树：
分析完上面的dfs，我们可以考虑如何用dp来解决问题。
先来考虑一下状态方程是什么？
dp[i][j]表示在前\(i\)件物品中选择若干件放入一个背包容量为\(j\)的背包可以获得的最大价值。
根据上方的图，我们可以看出，每一种物品选择就两种，选还是不选，那我考虑如果我们不选择第\(i\)件物品呢？我们发现如果我们不选择第\(i\)件物品，其实他的价值是等价于只选择\(i-1\)件物品的，因为我第\(i\)件物品并没有装入背包中，所以对背包的容量还是价值都不产生影响。所以我们可以得到不选的时候的状态方程：dp[i][j] = dp[i - 1][j] ，现在考虑选择了第\(i\)件物品，第\(i\)件物品的价格是\(v_i\)，重量是\(w_i\)，如果我们选择了\(i\)件物品，那么我最后的价值一定会加上\(v_i\)，并且我当前的物品是有重量的，我的背包是不是要至少留出\(w_i\)的空间，因为只有留出了\(w_i\)的空间，我们才能装的下第\(i\)件物品，当前背包是容量是\(j\)，要留下\(w_i\)的空间，那么背包至少有\(j-w_i\)的空间，所以我们得到转移方程：dp[i][j] = dp[i - 1][j - w[i]] + v[i]，为什么是i-1呢？因为我要把第\(i\)件物品放进去，前面的\(i-1\)件物品应该都是决策好的(可以选，可以不选)，并且背包还应该至少剩余j-w[i]的空间。如下图：
综上所述：状态转移方程是为：
dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - w[i]] + v[i])
请同学们好好理解\(01\)背包的方程，他是以后所有背包的基础！
注意边界值：应该是一件都不选，容量为0，价值为0。即dp[0][0] = 0
接下来我们看看代码：
#include <bits/stdc++.h>
using namespace std;
// dp[i][j] 表示从前 i 个物品中选体积不超过 j 的最大价值
int dp[40][210], w[40], v[40];// w和v分别表示物品的重量和价值
int main(){
int n, V; // n表示有多少种物品，V背包的体积
cin >> V >> n;
for(int i = 1; i <= n; i ++ ){ // 输入每种物品的重量和价值
cin >> w[i] >> v[i];
}
dp[0][0] = 0; // 一件物品也不选，他的价值是0 容量也是0 边界值
for(int i = 1; i <= n; i ++ ){ // 枚举选择第几件物品
for(int j = 0; j <= V; j ++ ){ // 枚举当前体积
dp[i][j] = dp[i - 1][j]; // 不选
if(w[i] <= j){ // 背包装得下才能选
dp[i][j] = max(dp[i][j], dp[i - 1][j - w[i]] + v[i]);
}
}
}
cout << dp[n][V]; // 从前n个物品中选，体积不超过V的最大价值
return 0;
}
同学们现在考虑一个问题：我们数组有没有必要开\(N \times V\) 的数组大小吗？同学们阅读到这里的时候可以自行思考一下。
首先肯定是没有必要的，为什么？我们重新聚焦于我们的状态转移方程：dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - w[i]] + v[i])，我们可以发现，对于每一个\(i\)，我们只用到了他的上一层也就是\(i - 1\)这一层，所以实际上我们只需要开一维长度为\(2\)的数组即可。即dp[2][V]即可。那考虑我们怎么样进行转移？很简单，我们知道当a[2]下标是0、1，其实就是一个奇数和一个偶数，如果\(i\)是奇数那么\(i - 1\)一定是偶数，反之如果\(i\)是偶数，\(i - 1\)一定是奇数，于是我们的状态转移方程就可以写成dp[i % 2][j] = max(dp[(i - 1) % 2][j], dp[(i - 1) % 2][j - w[i]] + v[i])
举例：
- 当\(i = 3\)的时候:
dp[i % 2][j] = dp[1][j] dp[i % 2][j] = dp[(i - 1) % 2][j] 等价于 dp[1][j] = dp[0][j] - 当\(i = 2\)的时候：
dp[i % 2][j] = dp[0][j] dp[i % 2][j] = dp[(i - 1) % 2][j] 等价于 dp[0][j] = dp[1][j]
于是我们就会发现，当\(i\)为偶数的时候,\(i - 1\)是奇数，反之是偶数，这样我们就可以通过长度为\(2\)的数组即\(0、1\)一直进行滚动，我们把这种空间优化称之为滚动数组优化
拓展：同学们可以想一下能不能直接把二维数组优化到一维呢？我们将会在后面的章节中进行介绍。现阶段同学们只需要掌握二维写法即可。
练习题：
完全背包
先来看一个简单的例题：完全背包问题I
有一个容量为 \(V\) 的背包，现有 \(N\) 种物品，重量别为 \(w_1,w_2,...,w_n\)，价值分别为 \(v_1v_2,...,v_n\), 若每种物品有无限多件，求能放入的大总价值。
同学们一眼看到这个题目的时候有没有觉得很疑惑？这个和01背包的区别在哪里？我们在01背包章节介绍了01背包的01就是一个物品只要一个，只有选不选两种可能。那我们来看看完全背包，完全背包是什么意思呢？完全背包和01背包不同点在于完全背包里面的物品有无数个！哇有好多金块！我们应该怎么做呢？首先还是应该考虑状态，现在的选择是每个物品取还是不取吗？不取的话还比较好理解，取的话由于每个物品有无数个，那你知道自己要取多少个吗？
细心的同学已经注意到了，完全背包问题我们要知道自己取几个，取\(0\)个、取\(1\)个、取\(2\)个、.....、取\(k\)个。 所以我们的状态划分就应该是取几个，那该如何写状态转移方程呢？我们一个一个看：设 \(w\)是重量，\(v\)是价值。
dp数组含义与 \(01\)背包相同。
情况一：当前体积为\(j\)
- 取\(0\)个：
dp[i][j] = dp[i - 1][j]; - 取\(1\)个：
dp[i][j] = dp[i - 1][j - w] + v; - 取\(2\)个：
dp[i][j] = dp[i - 1][j - 2w] + 2v; - 取\(k\)个：
dp[i][j] = dp[i - 1][j - kw] = kv;
我们的答案应该在上述的情况取一个max
所有有细心的同学已经发现了：我们要枚举我们取几个，这里我们又要一重循环，然后 k * w应该不能超过\(j\)，因为如果能装下k个物品，至少要留出j - k * w的空间。所以我们的核心代码如下：
注意：边界值任然是dp[0][0] = 0
for(int i = 1; i <= n; i ++ ){ // 枚举哪个物品
for(int j = 0; j <= m; j ++ ){ // 当前枚举的体积
for(int k = 0; k * w[i] <= j; k ++ ){ // 每一个物品体积是w[i] 一共有 k 个 所以 k * w[i] <= j j 为当前体积
dp[i][j] = max(dp[i-1][j], dp[i - 1][j - k * w[i]] + k * v[i]);
}
}
}
我们这里用了三重循环，考虑一下能否优化？
同学们可以自己想一下，然后在看下面的解释。
根据我们刚刚的推导，我们得到了：
dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - w] + v, dp[i - 1][j - 2w] + 2v, ... )
上面的推导式体积为\(j\)，我们现在考虑体积为\(j - w\)
dp[i][j - w] = max(dp[i - 1][j - w], dp[i - 1][j - 2w] + v, dp[i - 1][j - 3w] + 2v, ...)
继而得
dp[i][j - w] + v = max(dp[i - 1][j - w] + v, dp[i - 1][j - 2w] + 2v, dp[i - 1][j - 3w] + 3v, ...)
我们惊奇的发现，第一个式子的第二项开始其实就是第二个式子，所以我们就可以等价替换：
dp[i][j] = max(dp[i - 1][j], dp[i][j - w] + v)
如下图：
代码：
for(int i = 1; i <= n; i ++ ){
for(int j = 0; j <= m; j ++ ){
dp[i][j] = dp[i - 1][j]; // 不选
if(w[i] <= j){
dp[i][j] = max(dp[i][j], dp[i][j - w[i]] + v[i]);
}
}
}
练习题：
- 完全背包问题II 完全背包的优化(滚动数组)
- Money Systems 货币系统 完全背包求解方案数 难题
多重背包
同学们主要理解完全背包和\(01\)背包即可，多重背包大家可以自行理解一下。
先来看一个简单的例题：多重背包问题I
有 \(N\) 种物品和一个容量是 \(V\) 的背包。
第 \(i\) 种物品最多有 \(s_i\) 件，每件体积是 \(v_i\) ，价值是 \(w_i\) 。
求解将哪些物品装入背包，可使物品体积总和不超过背包容量，且价值总和最大。输出最大价值。
同学们可以看一下，多重背包和\(01\)背包和完全背包的区别在哪里？
细心的同学已经发现了，我们分组背包它每组物品是有限制的，不是无限个，那我们对于某一个物品，我们可以怎么样选择呢?
是不是对于某一个物品我们可以选择\(0个、1个、2个、3个、....、s_i个\)，于是我们发现，状态转移方程和完全背包没有进行优化的时候一模一样。
dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - w] + v, ..., dp[i - 1][j - sw] + sv)
如图：
代码：
for(int i = 1; i <= n; i ++ ){
for(int k = 0; k <= s[i]; k ++ ){
for(int j = 0; j <= m; j ++ ){
// 最多可以选择 s[i] 个 k 就是 0 ~ s[i]
if(k * v[i] <= j){
dp[i][j] = max(dp[i][j], dp[i -1][j - k * v[i]] + k * w[i]);
}
}
}
}
对于多重背包问题的优化，我们这里不在阐述，感兴趣的同学在我们以后的学习中，会和大家讲到。
对于多重背包的习题，大家先将例题做好即可。
分组背包
先来看一个简单的例题：分组背包问题
有 \(N\) 组物品和一个容量是 \(V\) 的背包。
每组物品有若干个，同一组内的物品最多只能选一个。每件物品的体积是 \(v_{ij}\) ，价值是 \(w_{ij}\) ，其中 \(i\) 是组号，\(j\) 是组内编号。
求解将哪些物品装入背包，可使物品总体积不超过背包容量，且总价值最大。
大家再来看看，分组背包和其他背包的区别是什么？有细心的同学已经注意到了，分组背包就是有很多组物品，然后每一组物品只能取一个。只能选一个？大家有没有恍然大悟!这不就是\(01\)背包吗？所以分组背包很简单，就是对于每一个组，我们组内做\(01\)背包即可，问题是如何分组，我们可以用vecotr<int> a也可以用w[i][j] 表示第i组第j个物品的重量，根据大家的喜好可以自行选择。
状态转移方程：
不选第\(i\)组物品的第\(j\)个，如果选的话要留出w[i][j]的空间。
dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - w[i][j]] + v[i][j] 其中 w[i][j] 表示第 i 组第 j 个物品的重量， v[i][j] 表示第 i 组物品第 j 个物品的价值
如图：
代码：
for(int i = 1; i <= n;i ++ ){
for(int j = 0; j <= m; j ++ ){
dp[i][j] = dp[i - 1][j]; //不选
for(int k = 0; k < s[i]; k ++ ){
if(j >= v[i][k]){
dp[i][j] = max(dp[i][j], dp[i - 1][j - v[i][k]] + w[i][k]);
}
}
}
}
分组背包我们目前阶段也不需要掌握，大家做会练习题即可。
到此我们的背包基本问题都已经给同学们分析完毕了，希望同学们好好理解01背包和完全背包，01背包是所有背包的入门。我们将会在下面的章节介绍线性动态规划。
混合背包
故名思意，混合背包就是所有背包的结合体，根据合适的 条件套用合适的背包模板即可。
优化
再谈01背包
根据我们上述所讲的，简单回顾一下01背包的状态。
dp[i][j] = dp[i - 1][j]，我们可以很容易的看出，每一次的i都应该与i-1有关，于是我们考虑如下的转移方程，把第一维度去掉：
for(int i = 1; i <= n; i ++ ){
for(int j = m; j >= v[i]; j -- ){
dp[i] = max(dp[i], dp[i - v[i]] + w[i]);
}
}
为什么内层循环是倒着枚举的？
我们先看为什么是到v[i]结束？这个很简单，如同我们上面说的，我们如果可以装得下，那必须要留够至少v[i]的空间。
在考虑为什么是倒着枚举？
我们知道每一个dp[i]应该只和dp[i - 1]有关。我们来看一下。
我们距离i = 2，j = 4的情况。
| j = 1 | j = 2 | j = 3 | |
|---|---|---|---|
| i = 1 | dp[1] | dp[2] = dp[2 - 1] + v[1] | dp[3] = dp[3 - 1] + v[2] |
| i = 2 | dp[1] | dp[2] = dp[2 - 1] + v[1] | dp[3] = dp[3 - 1] + v[2] |
简单看一下，当i = 2的时候，我们的转移方程一定是用到i = 1的时候的dp值，如果我们顺着枚举，由于\(v_i \geq 0\)所以\(j - v_i \leq j\)，如果我们从j = 1枚举到j = 3的话，会出现什么问题？例如当j= 3,dp[3] = dp[3 - 1] + v[2]，此时的dp[3 - 1]也就是dp[2]应该用到的是i = 1的情况，但是dp[2]我们在j = 2的情况更新过了，所以实际用到的是i = 2的情况的dp[i]，所以应该反着枚举。
再谈完全背包
考虑完全背包的方程，dp[i][j] = dp[i][j - v] + w
因为dp[i][j]和本层有关所以正着枚举即可。