我把该说的都在前面说了把
我这里的主旨是让大家系统的了解DP问题，将会把基础课/提高课DP题目全部讲一遍。这篇分享可能非常长！！！实在不行我就拆开。
长度甚至有可能超过这个！！！！提高课是在我另一个号上报的，如果你看不了提高课的题目也不要紧，每道题我都有简单的题目概括。

DP

$$第一章 \ \ 基本概念$$

$$这一章节的内容非(hao)常(wu)有(yong)用(chu)，能让你更好的理解DP的基本概念。$$

1.DP的定义

$ \ \ \ \ \ \ $ 动态规划（Dynamic Programming，DP）是运筹学的一个分支，是求解决策过程最优化的过程。20世纪50年代初，美国数学家贝尔曼（R.Bellman）等人在研究多阶段决策过程的优化问题时，提出了著名的最优化原理，从而创立了动态规划。

2.DP的概念引入

$ \ \ \ \ \ \ $ 在现实生活中，有一类活动的过程，由于它的特殊性，可将过程分成若干个互相联系的阶段，在它的每一阶段都需要作出决策，从而使整个过程达到最好的活动效果。因此各个阶段决策的选取不能任意确定，它依赖于当前面临的状态，又影响以后的发展。当各个阶段决策确定后，就组成一个决策序列，因而也就确定了整个过程的一条活动路线．这种把一个问题看作是一个前后关联具有链状结构的多阶段过程就称为多阶段决策过程，这种问题称为多阶段决策问题。在多阶段决策问题中，各个阶段采取的决策，一般来说是与时间有关的，决策依赖于当前状态，又随即引起状态的转移，一个决策序列就是在变化的状态中产生出来的，故有“动态”的含义，称这种解决多阶段决策最优化的过程为动态规划方法。

3.DP的基本思想

$ \ \ \ \ \ \ $ 动态规划算法通常用于求解具有某种最优性质的问题。在这类问题中，可能会有许多可行解。每一个解都对应于一个值，我们希望找到具有最优值的解。动态规划算法与分治法类似，其基本思想也是将待求解问题分解成若干个子问题，先求解子问题，然后从这些子问题的解得到原问题的解。与分治法不同的是，适合于用动态规划求解的问题，经分解得到子问题往往不是互相独立的。若用分治法来解这类问题，则分解得到的子问题数目太多，有些子问题被重复计算了很多次。如果我们能够保存已解决的子问题的答案，而在需要时再找出已求得的答案，这样就可以避免大量的重复计算，节省时间。我们可以用一个表来记录所有已解的子问题的答案。不管该子问题以后是否被用到，只要它被计算过，就将其结果填入表中。这就是动态规划法的基本思路。具体的动态规划算法多种多样，但它们具有相同的填表格式。

4.DP的基本概念

（1）多阶段决策问题

$ \ \ \ \ \ \ $ 如果一类活动过程可以分为若干个互相联系的阶段，在每一个阶段都需作出决策（采取措施），一个阶段的决策确定以后，常常影响到下一个阶段的决策，从而就完全确定了一个过程的活动路线，则称它为多阶段决策问题。
$ \ \ \ \ \ \ $ 各个阶段的决策构成一个决策序列，称为一个策略。每一个阶段都有若干个决策可供选择，因而就有许多策略供我们选取，对应于一个策略可以确定活动的效果，这个效果可以用数量来确定。策略不同，效果也不同，多阶段决策问题，就是要在可以选择的那些策略中间，选取一个最优策略，使在预定的标准下达到最好的效果。

（2）动态规划问题中的术语

$ \ \ \ \ \ \ $ 阶段：把所给求解问题的过程恰当地分成若干个相互联系的阶段，以便于求解，过程不同，阶段数就可能不同．描述阶段的变量称为阶段变量。在多数情况下，阶段变量是离散的，用k表示。此外，也有阶段变量是连续的情形。如果过程可以在任何时刻作出决策，且在任意两个不同的时刻之间允许有无穷多个决策时，阶段变量就是连续的。
$ \ \ \ \ \ \ $ 状态：状态表示每个阶段开始面临的自然状况或客观条件，它不以人们的主观意志为转移，也称为不可控因素。就是某阶段的出发位置，它既是该阶段某路的起点，同时又是前一阶段某支路的终点。
$ \ \ \ \ \ \ $ 无后效性：我们要求状态具有下面的性质：如果给定某一阶段的状态，则在这一阶段以后过程的发展不受这阶段以前各段状态的影响，所有各阶段都确定时，整个过程也就确定了。换句话说，过程的每一次实现可以用一个状态序列表示，在前面的例子中每阶段的状态是该线路的始点，确定了这些点的序列，整个线路也就完全确定。从某一阶段以后的线路开始，当这段的始点给定时，不受以前线路（所通过的点）的影响。状态的这个性质意味着过程的历史只能通过当前的状态去影响它的未来的发展，这个性质称为无后效性。
$ \ \ \ \ \ \ $ 决策：一个阶段的状态给定以后，从该状态演变到下一阶段某个状态的一种选择（行动）称为决策。在最优控制中，也称为控制。在许多问题中，决策可以自然而然地表示为一个数或一组数。不同的决策对应着不同的数值。描述决策的变量称决策变量，因状态满足无后效性，故在每个阶段选择决策时只需考虑当前的状态而无须考虑过程的历史。另外，决策变量的范围称为允许决策集合。
$ \ \ \ \ \ \ $ 策略：由每个阶段的决策组成的序列称为策略。对于每一个实际的多阶段决策过程，可供选取的策略有一定的范围限制，这个范围称为允许策略集合，允许策略集合中达到最优效果的策略称为最优策略。
$ \ \ \ \ \ \ $ 状态转移方程：两个状态转移的递推关系式，动态规划中本阶段的状态固定是上一阶段状态和上一阶段决策的结果。
$ \ \ \ \ \ \ $ 最优化原理：作为整个过程的最优策略，它满足：相对前面决策所形成的状态而言，余下的子策略必然构成“最优子策略”，最优性原理实际上是要求问题的最优策略的子策略也是最优。

5.基本结构

$ \ \ \ \ \ \ $ 多阶段决策问题中，各个阶段采取的决策，一般来说是与时间有关的，决策依赖于当前状态，又随即引起状态的转移，一个决策序列就是在变化的状态中产生出来的，故有“动态”的含义，称这种解决多阶段决策最优化问题的方法为动态规划方法。

6.适用条件

最优化原理（最优子结构性质）

$ \ \ \ \ \ \ $ 最优化原理可这样阐述：一个最优化策略具有这样的性质，不论过去状态和决策如何，对前面的决策所形成的状态而言，余下的诸决策必须构成最优策略。简而言之，一个最优化策略的子策略总是最优的。一个问题满足最优化原理又称其具有最优子结构性质。

无后效性

$ \ \ \ \ \ \ $ 将各阶段按照一定的次序排列好之后，对于某个给定的阶段状态，它以前各阶段的状态无法直接影响它未来的决策，而只能通过当前的这个状态。换句话说，每个状态都是过去历史的一个完整总结。这就是无后向性，又称为无后效性。

子问题的重叠性

$ \ \ \ \ \ \ $ 动态规划算法的关键在于解决冗余，这是动态规划算法的根本目的。动态规划实质上是一种以空间换时间的技术，它在实现的过程中，不得不存储产生过程中的各种状态，所以它的空间复杂度要大于其他的算法。选择动态规划算法是因为动态规划算法在空间上可以承受，而搜索算法在时间上却无法承受，所以我们舍空间而取时间。

7.分类

这里在百度上的解释过于深奥无用，我这里说几个DP的知识点分类。

背包DP
线性DP
区间DP
状态压缩DP
树形DP
记忆化DP
计数DP
数位统计DP
状态机DP
优化DP
1. 单调队列优化DP
2. 斜率优化DP
3. 四边形不等式优化DP
4. …
模型
1. 数字三角形模型
2. 最长上升子序列模型
3. …
基环树DP
插头DP
…

8.局限性

$ \ \ \ \ \ \ $ 动态规划对于解决多阶段决策问题的效果是明显的，但是动态规划也有一定的局限性。首先，它没有统一的处理方法，必须根据问题的各种性质并结合一定的技巧来处理；另外当变量的维数增大时，总的计算量及存贮量急剧增大。因而，受计算机的存贮量及计算速度的限制，当今的计算机仍不能用动态规划方法来解决较大规模的问题，这就是“维数障碍”。

$$理解了这些术语，可我们怎么解决DP问题呢？跟我一起走进下一章！$$

$$第二章 \ \ 解决方案$$

$$上一章，我们学习了DP是什么东西，现在，是时候学习怎么解决DP问题了！$$

这就引出了我们的——

$$ 闫氏DP分析法 $$

话不多说，现在我们就开始认识闫氏DP分析法。先从一张图开始。

现在我们就用 $\color{red}{“树”}$ 来理解一下这幅图。

DP
- 状态表示
  - 集合
    - 所有满足xx的xx集合——数组 $f[i][j]$ 的含义
    - 确定所属模型——这个在写的时候不用写出来，你只要看懂这是什么类型的DP就行了，前面有介绍。
  - 属性——分为三大类：最大最小，个数，是否。表示最优策略的判断方法，也就是所以决策的判断方法。
- 状态计算
  - 划分为多少子集——有哪些决策。
  - 划分准则——不重复，不遗漏（求最大最小是可以重复）。
  - 划分技巧——可以从最后一个与其他决策不同点入手。

解决问题有三部曲：

考虑数组的含义（状态表示——集合）
确定属性（状态表示——属性）
由数组的含义与属性推出状态转移方程（状态计算——集合划分）

时间复杂度：
$$学会了方法，可是怎么应用呢？跟我一起走进下一章！$$

$$第三章 \ \ 解决问题$$

$$上一章，我们学习了解决问题的方法，现在是时候解决一些问题了！$$

背包DP

背包DP非常经典，每个OIer都应该掌握，我们现在从最基础的学起

01背包问题

题目相当于要你选若干个物品，让他们的体积不超过背包容量，且价值最大。
是时候用上三部曲了！

状态表示——集合：$f[i][j]$ 表示考虑前 $i$ 个物品，且总体积不超过 $j$ 的集合下能获得的最大价值。
状态表示——属性：因为是求最大价值，故为 $max$。
状态计算——集合划分：考虑第 $i$ 个选不选。
- 不选或选不了（剩余体积不够 $j < v[i]$）：$f[i - 1][j]$。
- 选：$f[i - 1][j - v[i]] + w[i]$。

那么代码里就这么写：

1
2
3

f[i][j] = f[i - 1][j]; //不选，这种情况绝对可以选择
if (j >= v[i]) //体积必须足够，否则不能放置
    f[i][j] = max(f[i][j], f[i - 1][j - v[i]] + w[i]); //选，花费v[i]的体积，获得w[i]的价值

完整代码，时间复杂度：$O(nm)$

#include <iostream>
using namespace std;

const int N = 1010;
int n, m;
int v[N], w[N];
int f[N][N];

int main() {
    cin >> n >> m;
    for (int i = 1; i <= n; i ++ ) cin >> v[i] >> w[i];
    
    for (int i = 1; i <= n; i ++ ) 
        for (int j = 1; j <= m; j ++ ) {
            f[i][j] = f[i - 1][j];
            if (j >= v[i]) f[i][j] = max(f[i][j], f[i - 1][j - v[i]] + w[i]);
        }
    cout << f[n][m];
    return 0;
}

然后我想啊想，那第一维只考虑到 $i - 1$ 能不能优化呢？

能！

我们用滚动数组优化，f[1][j]放到f[1][j]，f[2][j]放到f[0][j]，f[3][j] 可以覆盖f[1][j]，也就是放到f[i & 1][j]上...这里可以直接把每个用到 $f$ 的位置 &1 就可以了。&1就相当于%2。

另：之后的问题我就不写滚动数组了，滚动数组只是能优化空间，不在空间不足的情况下无需使用。

滚动数组也就相当于反复覆盖之前无用的空间而已

也就相当于：

1	f[i][j] = f[i & 1][j]

举个栗子：

f[1][j] = f[1][j]
f[2][j] = f[0][j]
f[3][j] = f[1][j]
f[4][j] = f[0][j]

然而并不会影响结果，因为每次覆盖的都是没有用的。

完整代码，时间复杂度：$O(nm)$

#include <iostream>
using namespace std;

const int N = 1010;
int n, m;
int v[N], w[N];
int f[2][N];

int main() {
    cin >> n >> m;
    for (int i = 1; i <= n; i ++ ) cin >> v[i] >> w[i];
    
    for (int i = 1; i <= n; i ++ ) 
        for (int j = 1; j <= m; j ++ ) {
            f[i & 1][j] = f[i - 1 & 1][j];
            if (j >= v[i]) f[i & 1][j] = max(f[i & 1][j], f[i - 1 & 1][j - v[i]] + w[i]);
        }
    cout << f[n & 1][m];
    return 0;
}

现在我要得寸进尺，能不能把第一维直接省去呢？

能！！！

但不能像之前直接更改了，因为更新 $f[j]$ 的已经被更新过，不能再次更新，需要将体积倒着枚举，这样的话：
f[j]没有被更新过，而且f[j - v[i]]由于j - v[i]比j小，没有被遍历过，也就是 i - 1更新的东西，这样就可以了。

完整代码，时间复杂度：$O(nm)$

#include <iostream>
using namespace std;

const int N = 1010;
int n, m;
int v[N], w[N];
int f[N];

int main() {
    cin >> n >> m;
    for (int i = 1; i <= n; i ++ ) cin >> v[i] >> w[i];
    
    for (int i = 1; i <= n; i ++ ) 
        for (int j = m; j >= v[i]; j -- ) { //体积小于v[i]的f不会被更新，所以只需遍历到v[i]
            f[j] = max(f[j], f[j - v[i]] + w[i]); //现在的f[j]就是f[i - 1][j]，并且可以选择i
            //而f[j - v[i]]没有被更新，所以就又变成了f[i][j] = max(f[i][j], f[i - 1][j - v[i]] + w[i]);
        }
    cout << f[m];
    return 0;
}

了解完01背包，我们再来看一看完全背包。
完全背包问题
完全背包跟01背包好像并没什么不同，只是一个物品可以放多个而已。
那我们就直接枚举当前物品用多少个就行了。

完整代码，时间复杂度：$O(nm^2)$

#include <iostream>

using namespace std;

const int N = 1100;
int n, m;
int v[N], w[N];
int f[N][N];

int main() {
    int n, m;
    cin >> n >> m;
    for (int i = 1; i <= n; i ++ ) cin >> v[i] >> w[i];
    for (int i = 1; i <= n; i ++ ) {
        for (int j = 1; j <= m; j ++ ) {
            f[i][j] = f[i - 1][j];
            for (int k = 1; k <= j / v[i]; k ++ ) {
                f[i][j] = max(f[i][j], f[i - 1][j - k * v[i]] + k * w[i]);
            }
        }
    }
    cout << f[n][m] << endl;
    return 0;
}

但是这样会 $\color{blue}{TLE}$，所以我们要考虑优化，那我们在选一个物品后，能不能继续考虑前i个物品呢？
那么我们可以看一个图了解一下。

1
2

f[i, j] = max(f[i - 1, j], f[i - 1, j - v] + w,  f[i - 1, j - 2 * v] + 2 * w, f[i - 1, j - 3 * v] + 3 * w, ...)
f[i, j - v] = max(         f[i - 1, j - v]    ,  f[i - 1, j - 2 * v] + w    , f[i - 1, j - 3 * v] + 2 * w...)

我们惊奇的发现，除了 $f[i][j]$ 第一项的不选之外，每一项都与下面差一个 $w$ ，那么除了第一项以外的决策的最大值与 $f[i][j - v]$ 的值只相差一个 $w$ ，只需在 $f[i][j - v]$ 的基础上加一个 $w$ 即可，那么我们就可以把状态转移方程变成这样：
f[i][j] = max(f[i][j], f[i][j - v] + w);
这样就可以通过了。

完整代码，时间复杂度：$O(nm)$

#include <iostream>

using namespace std;

const int N = 1100;
int n, m;
int v[N], w[N];
int f[N][N];

int main() {
    int n, m;
    cin >> n >> m;
    for (int i = 1; i <= n; i ++ ) cin >> v[i] >> w[i];
    for (int i = 1; i <= n; i ++ ) {
        for (int j = 1; j <= m; j ++ ) {
            f[i][j] = f[i - 1][j];
            if (j >= v[i]) 
                f[i][j] = max(f[i][j], f[i][j - v[i]] + w[i]);
        }
    }
    cout << f[n][m] << endl;
    return 0;
}

然后我们可以用类似01背包的方式来省去第一维，注意这回背包大小不是倒着枚举，因为这回我们转移到当前状态的应该是已经被第 $i$ 个物品更新过的，与01背包不同，所以需要正着枚举。

完整代码，时间复杂度：$O(nm)$

#include <iostream>

using namespace std;

const int N = 1100;
int n, m;
int v[N], w[N];
int f[N];

int main() {
    int n, m;
    cin >> n >> m;
    for (int i = 1; i <= n; i ++ ) cin >> v[i] >> w[i];
    for (int i = 1; i <= n; i ++ ) {
        for (int j = v[i]; j <= m; j ++ ) {
            f[j] = max(f[j], f[j - v[i]] + w[i]);
        }
    }
    cout << f[m] << endl;
    return 0;
}

多重背包问题1 多重背包问题2 多重背包问题3
多重背包问题只不过是在完全背包的基础上有了一个数量的限制，所以我们只需要在加一层循环枚举个数就行了。

完整代码，时间复杂度：$O(nms)$

#include <iostream>
using namespace std;

const int N = 110;
int n, m;
int v[N], w[N], s[N];
int f[N][N];

int main() {
    cin >> n >> m;
    for (int i = 1; i <= n; i ++ ) cin >> v[i] >> w[i] >> s[i];
    
    for (int i = 1; i <= n; i ++ )
        for (int j = 1; j <= m; j ++ ) {
            f[i][j] = f[i - 1][j];
            for (int k = 1; k * v[i] <= j && k <= s[i]; k ++ ) //枚举选的个数，但要判断能不能装下。
                f[i][j] = max(f[i][j] , f[i - 1][j - k * v[i]] + k * w[i]);
        }
    cout << f[n][m] << endl;
    return 0;
}

那你就会问了，同样的题你贴三遍干啥？那现在我们进入多重背包问题2！！！
这道题与上一道题相同，但增大了数据范围，意味着刚才的暴力将会 $\color{green}{TLE}$
那我们能不能用想刚才完全背包一样优化呢？我们来试一试，就会发现是这样：

1
2

f[i][j] = max(f[i - 1][j], f[i - 1][j - v] + w, f[i - 1][j - 2v] + 2w, ....., f[i - 1][j - sv] + sw);
f[i][j - v] = max(       , f[i - 1][j - v]    , f[i - 1][j - 2v] + w , ....., f[i - 1][j - sv] + (s - 1)w, f[i - 1][j - (s + 1)v] + sw);

这后面这一坨啊，和我们下面这些非常相似的对吧，但是呢，比较 $\color{red}{蛋疼}$ 的是f[i][j - v]多了一项对吧 -yxc

那我们能不能求出前面的最大值呢？不行。问题就像这样：给你所有数的最大值以及最后一个数，你能不能求出前面几项的大值呢？如果你做到了，请立即私信我！！！
所以我们不能用这种方式直接优化。

但我们可以用二进制优化方式！！！！！
假设我们想去凑出来 $s$ 的话，假设我们有 $1023$ 个数，我们真的需要从 $0$ 枚举到 $1023$ 吗？
我们可以把若干个第 $i$ 个物品打包到一块考虑。例如说我们打包 $10$ 组，分别有 1,2,4,8,16...,512 个物品，然后每组最多只能选一次。

又有人要问了，这样一定能凑出从 $0$ 到 $1023$ 中的所有数吗？可以，因为这不就是一位一位的二进制表示吗，用二进制表示可以表示从 $0$ 到 $1023$ 的所有数！当然也可以这样想：
首先我使用 $1$ ，可以凑出 $0-1$ 的所有数，接下来我把 $0-1$ 的所有数都加上 $2$ ，就可以凑出 $0-3$ ……，这样就可以一直凑到 $1023$。

然后 1,2,4,8,16...,512 每一组都可以看成是一个01背包里的物品，也就是我们用了 $10$ 个新的物品来代替我们第 $i$ 个物品，就可以只用 $10$ 次枚举出 $1024$ 种了。如此下来，每一种物品都变成了 $10$ （其实是 $logs$）个物品，每个物品只能选一个，这样问题就变成了一个01背包问题。

完整代码，时间复杂度：$O(nmlogs)$

#include <iostream>
#include <algorithm>

using namespace std;

const int N = 12010, M = 2010;

int n, m;
int v[N], w[N];
int f[M];

int main()
{
    cin >> n >> m;

    int cnt = 0;
    for (int i = 1; i <= n; i ++ )
    {
        int a, b, s;
        cin >> a >> b >> s;
        int k = 1;
        while (k <= s)
        {
            cnt ++ ;
            v[cnt] = a * k; //把一个物品拆分成logs个物品。
            w[cnt] = b * k;
            s -= k;
            k *= 2;
        }
        if (s > 0)
        {
            cnt ++ ;
            v[cnt] = a * s; //由于是一个一个往上拆，最后有可能剩下一些物品，也同样要加进去。
            //除非你倒着拆，直接把它拆成2进制数，同样也是可以的。
            //在这里，例如8，先拆掉一个1，再拆一个2，再拆一个4，最后剩下一个1。
            w[cnt] = b * s;
        }
    }

    n = cnt;

    for (int i = 1; i <= n; i ++ )
        for (int j = m; j >= v[i]; j -- )
            f[j] = max(f[j], f[j - v[i]] + w[i]);  //最后再这些物品中进行01背包

    cout << f[m] << endl;

    return 0;
}

你可能会说：这已经很难了，难道还有比这个更难的？有！让我们一起看多重背包问题3
首先我们还是得从公式入手。

你会发现，能转移到 $f[i][j]$ 无非就从 $f[i - 1][j - v]$ 到 $f[i - 1][j - sv]$，那你在来看看这幅图。$r$ 就是 $j % v$ 的余数，像此图中，$r +5v$ 就可以从 $r -> r + 4v$ 之间的最大值转移过来。

这就像一个滑动窗口,那么我们就可以用滑动窗口解决此问题。

其实你由此会发现一个性质：完全背包就是前缀最大值，多重背包就是滑动窗口。

完整代码，时间复杂度：$O(nm)$

#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;

const int N = 20010;
int n, m;
int f[N], g[N], q[N];
//拷贝数组，因为这里不能使用一维优化，因为如果倒叙枚举，你就不能用滑动窗口了。

int main()
{
    cin >> n >> m;
    for (int i = 1; i <= n; i ++ ) {
        int v, w, s;
        cin >> v >> w >> s;
        memcpy(g, f, sizeof f);
        for (int j = 0; j < v; j ++ ) {
            int hh = 0, tt = -1;
            for (int k = j; k <= m; k += v) {
                if (hh <= tt && q[hh] < k - s * v) hh ++ ; //剔除超出长度元素
                if (hh <= tt) f[k] = max(f[k], g[q[hh]] + (k - q[hh]) / v * w); //更新当前答案
                while (hh <= tt && g[q[tt]] - (q[tt] - j) / v * w <= g[k] - (k - j) / v * w) tt -- ;
                //维持单调性
                //这里也可以这样写，更易理解
                //while (hh <= tt && g[q[tt]] <= g[k] - (k - q[tt]) / v * w) tt -- ;
                q[ ++ tt] = k;
            } 
        }
    }
    cout << f[m] << endl;
    return 0;
}

接下来我们来了解分组背包问题，这是基础课最后一道背包题了，之前只讲过一道提高课背包问题——多重背包问题3，讲完这道题我们开始讲提高课题目。
相当于在问你每组物品里最多选一个，问最大价值。
首先我们在最外边枚举每一组，里面的 $f[j]$ 表示总体积为 $j$ 能获得的最大价值。
但里边有一些不同点，这里必须先枚举体积，再枚举每一个物品。因为如果先枚举物品，那么你下一个物品不管从哪里转移都已经被上一个更新，同时，体积必须倒着枚举，否则一个物品将会被重复选择。

完整代码，时间复杂度：$O(nms)$

#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;

const int N = 110;
int n, m;
int v[N], w[N];
int f[N];

int main() {
    cin >> n >> m;
    for (int i = 1; i <= n; i ++ ) {
        int a;
        cin >> a;
        for (int j = 1; j <= a; j ++ ) {
            cin >> v[j] >> w[j];
        }
        for (int j = m; j >= 0; j -- ) { //先枚举体积，倒着枚举这样就不会被自己更新
            for (int k = 1; k <= a; k ++ ) { //在枚举每一个
                if (j >= v[k]) //这里与其他01背包有些不同，因为在枚举j的时候还没有枚举每一个数，故需特判
                    f[j] = max(f[j], f[j - v[k]] + w[k]);
            }
        }
        
    }
    cout << f[m] << endl;
    return 0;
}

好的，休息片刻，我来讲提高课背包问题。
2000years later…..
好，现在我们来看第一道题——采药
这道题的题目大意就是给你一些物品然后给你一些时间，每个物品想要拿到需要时间，并会获得一定的价值，问最大价值
这不就是我们众所周知的01背包问题吗，只要把时间转换成 背包大小，搞到一个物品的时间变为体积就可以了。其他像一维优化的我就不讲了，01背包那里都讲过了。

完整代码，时间复杂度：$O(nm)$

#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;

const int N = 110;
int n, m;
int v[N], w[N];
int f[N][N * 10];

int main()
{
    cin >> m >> n;
    for (int i = 1; i <= n; i ++ ) cin >> v[i] >> w[i];
    for (int i = 1; i <= n; i ++ ) {
        for (int j = 1; j <= m; j ++ ) {
            f[i][j] = f[i - 1][j];
            if (j >= v[i]) f[i][j] = max(f[i][j], f[i - 1][j - v[i]] + w[i]);
        }
    }
    cout << f[n][m] << endl;
    return 0;
}

DP

$$第一章 \ \ 基本概念$$

1.DP的定义

2.DP的概念引入

3.DP的基本思想

4.DP的基本概念

（1）多阶段决策问题

（2）动态规划问题中的术语

5.基本结构

6.适用条件

7.分类

8.局限性

$$第二章 \ \ 解决方案$$

$$ 闫氏DP分析法 $$

$$第三章 \ \ 解决问题$$

背包DP

01背包问题

完整代码，时间复杂度：$O(nm)$

能！

另：之后的问题我就不写滚动数组了，滚动数组只是能优化空间，不在空间不足的情况下无需使用。

也就相当于：

举个栗子：

完整代码，时间复杂度：$O(nm)$

能！！！

完整代码，时间复杂度：$O(nm)$

完整代码，时间复杂度：$O(nm^2)$

完整代码，时间复杂度：$O(nm)$

完整代码，时间复杂度：$O(nm)$

完整代码，时间复杂度：$O(nms)$

完整代码，时间复杂度：$O(nmlogs)$

其实你由此会发现一个性质：完全背包就是前缀最大值，多重背包就是滑动窗口。

完整代码，时间复杂度：$O(nm)$

完整代码，时间复杂度：$O(nms)$

完整代码，时间复杂度：$O(nm)$

考试当天

T1

T2

T3

T4

出去后

第二天自测