🪜动态规划

动态规划：dynamic programming DP
闫氏 DP 分析法：
- 1). 状态表示
  - 集合：f[i][j] 表示哪一类的集合
  - 属性： Max / Min / Count
- 2). 状态计算 -- 集合的划分
  - f[i][j] 这个集合可以从哪些集合经过计算后转移过来

一、背包问题

1.1 01 背包

每件物品最多用 1 次。
模板题：2. 01背包问题
1). 朴素写法 - 二维 - 最接近分析的本质

c++

#include <iostream>
#include <algorithm>
using namespace std;

const int N = 1010;
// 物品数量 n 和 背包容积 m
int n,m;
// 每一件物品的体积和价值
int v[N], w[N];
// f[i][j] : 前 i 件物品当中选，体积不超过 j 的情况下可以取得的物品最大值
int f[N][N];

int main()
{
    cin >> n >> m;
    // 读入每一个物品
    for(int i = 1; i <= n; i ++ ) cin >> v[i] >> w[i];
    // 其实这里应该有f[][] 的初始化
    // 如 : f[0][0~m] : 没有物品，各种容量，显然最大价值是 0
    // f[0~n][0] : 各种物品，没有容量，显然最大价值也是 0
    // 又因为我们的 f[][] 是定义在全局，所以默认是 0
    // 则下面做 dp 的时候两个维度都可以从 1 开始
    for(int i = 1; i <= n; i ++ )
        for(int j = 1; j <= m; j ++ )
        {
            f[i][j] = f[i - 1][j];  // 不选第 i 件
            if(j >= v[i]){  // 背包容量允许的情况下选第 i 件物品
                f[i][j] = max(f[i][j], f[i - 1][j - v[i]] + w[i]);
            }
        }
    cout << f[n][m] << endl;
    return 0;
}

我们可以发现：在一维层面 f[i][] 这层只用到了上一层 f[i - 1][]
那么我们可以用滚动数组的思想优化成一维来做

📌 注意：滚动数组的关键点

思考第二维循环，在朴素写法中，有 if(j >= v[i]) , 也就是说，其实 j 小于 v[i] 是没必要遍历的，

但难道就写成 for(int j = v[i]; j <= m; j ++ ) 吗？？这是经典的错误，思考这个循环的遍历方向

j 是从左循环到右的，也就是说，如果我们在左侧部分列更新了 f[j] ，那么在 f[j - v[i]] 这个

表达式用的就是本层刚更新的值，而且不是用到我们刚刚分析的用上一层的值，所以正确的应该是

写成从右到左遍历，那么滚动数组只会用到上一层更新的值 for(int j = m; j >= v[i]; j -- )

1. . 使用滚动数组优化成一维

c++

#include <iostream>
#include <algorithm>
using namespace std;

const int N = 1010;
// 物品数量 n 和 背包容积 m
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 -- )
            f[j] = max(f[j], f[j - v[i]] + w[i]);
            
    cout << f[m] << endl;
    return 0;
}

1.2 完全背包

每件物品可用无限次。
模板题：AcWing 3. 完全背包问题
1). 朴素做法，集合可以拆分成取 k 个第 i 个物品， k * v[i] <= j
注意：现在的朴素做法在 acwing 上会 TLE （可以帮助理解过程）

c++

#include <iostream>
#include <algorithm>
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 ++)
            for(int k = 0; k * v[i] <= j; 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;
}

写出 f[i, j] 和 f[i, j - v] 会惊奇的发现：

也就是说 f[i][j] 可以写成 f[i][j] = Max(f[i - 1][j], f[i, j - v] + w)
其实也很好理解对吧，换成中文描述就是从前 i 个物品中选且体积不超过 j 可以
获得的最大价值可以划分成，要不不取第 i 件物品，也就是 f[i - 1][j] ,
要不就是取第 i 件物品，取一次加一次 w ，但是我们这里不会像 01背包 那样找
只能第 i - 1 的，因为我们第 i 件可以反复取

2). 根据发现的规律进行优化：三维循环 -> 二维循环

c++

#include <iostream>
#include <algorithm>
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];  // 不取第 i 件物品
            // 如果容量允许的情况下取第 i 件物品
            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背包 ＆ 完全背包 的状态转移方程：
- 01背包 ： f[i][j] = Max(f[i - 1][j] , f[i - 1][j - v[i]] + w[i])
- 完全背包 ：f[i][j] = Max(f[i - 1][j] , f[i][j - v[i]] + w[i])
可以发现，01背包 是从第 i - 1 层转移过来，而 完全背包 是从第 i 层转移过来
📌 不要不以为意，这是优化成滚动数组的关键，前面我们要找上一层，所以我们的 j
需要转化为从右到左遍历才能正确的取值，这里要找当前层，所以我们就需要按正常
的从左到右遍历才是正确的取值【一定要想懂 01 ＆ 完全 的最终写法只差了个遍历顺序这件事】
3). 优化成滚动数组 --> 一维的存储（完全背包的终极写法）

c++

#include <iostream>
#include <algorithm>
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 = v[i]; j <= m; j ++)
            f[j] = max(f[j], f[j - v[i]] + w[i]);
    cout << f[m] << endl;    
    return 0;
}

1.3 多重背包

第 i 件物品有 s_i 个。
模板题：4. 多重背包问题 I
1). 朴素写法：（和多重背包朴素写法分析类似）

c++

#include <iostream>
#include <algorithm>
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 ++ )
            for(int k = 0; k <= s[i] && k * v[i] <= j; k ++ )   // 不超过数量 s[i], k*v[i] 不超过容积 j
            {
                f[i][j] = max(f[i][j], f[i - 1][j - v[i] * k] + w[i] * k);
            }
    
    cout << f[n][m] << endl;
    return 0;
}

二进制拆分优化：把 “有 s 个” 的物品拆成 1,2,4,8… 的不同数量的 “捆绑件” ，不足补余数。
这些 2 的幂次能拼出 0~s 的任意数，于是把 “拿多少个” 转化成 “ 拿哪几个捆绑件” 。
拆完只剩 O(log s) 个 01 背包，总复杂度从 O(N·V·s) 降到 O(N·V·log s) 。
模板题：5. 多重背包问题 II
2). 二进制拆分优化：（拆分后就可以看作 01 背包来做）

c++

#include <iostream>
#include <algorithm>
using namespace std;
const int N = 25000, M = 2010;

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

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;  // 当前捆的数量 (2 的 0 次方)
        while(k <= s){
            cnt ++;
            v[cnt] = a * k;
            w[cnt] = b * k;
            s -= k;
            k *= 2;
        }
        if(s > 0){
            // 如果还有剩余的，再加一捆
            cnt ++ ;
            v[cnt] = a * s;
            w[cnt] = b * s;
        }
    }
    
    // 接下来就是做一遍 01 背包问题
    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]);
    
    cout << f[m] << endl;    
    return 0;
}

1.4 分组背包

物品分若干组，每组最多选 1 件。
模板题：9. 分组背包问题
示例代码：

c++

#include <iostream>
#include <algorithm>
using namespace std;
const int N = 110;

int n, m;
// v/w[i][j] : 表示第 i 组物品中第 k 个物品的体积/价值
// s[i] : 第 i 组物品的物品数量
int v[N][N], w[N][N], s[N];
int f[N];

int main()
{
    cin >> n >> m;
    for(int i = 1; i <= n; i ++ ){
        cin >> s[i];    // 第 i 组物品的物品数量 
        for(int j = 1; j <= s[i]; j ++ ){
            // 读入 s[i] 个物品属性
            cin >> v[i][j] >> w[i][j];
        }
    }
    
    for(int i = 1; i <= n; i ++ )
        for(int j = m; j >= 1; j -- )
            for(int k = 1; k <= s[i]; k ++ )
                if(v[i][k] <= j)
                    f[j] = max(f[j], f[j - v[i][k]] + w[i][k]);
                    
    cout << f[m] << endl;
    return 0;
}

二、线性 DP

2.1 数字三角形

模板题：898. 数字三角形
示例代码：

c++

#include <iostream>
#include <algorithm>
using namespace std;

const int N = 510, INF = 1e9;
int a[N][N];
int f[N][N];

int main()
{
    int n;
    scanf("%d", &n);
    
    // 读入三角形(下标从 1 开始)
    for(int i = 1; i <= n; i ++ )
        for(int j = 1; j <= i; j ++)
            scanf("%d", &a[i][j]);
    
    // 初始化 f
    for(int i = 0; i <= n; i ++ )
        for(int j = 0; j <= i + 1; j ++ )   // 这里注意要多初始两个位置 0 / i + 1, 因为递推从左上和右上来
            f[i][j] = -INF;
            
    // 起点的 f 结果就是它本身
    f[1][1] = a[1][1];
    // 递推
    // i 从 2 开始
    for(int i = 2; i <= n; i ++ )
        for(int j = 1; j <= i; j ++ )
            f[i][j] = max(f[i - 1][j - 1], f[i - 1][j]) + a[i][j];
        
    // 递推完后再找最后一行的 max
    int res = -INF;
    for(int i = 1; i <= n; i ++ ) res = max(res, f[n][i]);
    
    cout << res << endl;
    
    return 0;
}

2.2 最长上升子序列

模板题：895. 最长上升子序列
示例代码：

c++

#include <iostream>
#include <algorithm>
using namespace std;
const int N = 1010;

int n;
// f[i] : 指以第 i 个数结尾的子序列长度最大值
int a[N], f[N];

int main()
{
    cin >> n;
    // 读入序列
    for(int i = 1; i <= n; i ++ ) cin >> a[i];
    for(int i = 1; i <= n; i ++ ){
        f[i] = 1;   // 每一个 f 最小都是 1 ，因为有 a[i] 本身
        for(int j = 1; j < i; j ++ ){
            if(a[j] < a[i]){
                // 如果前面的某个数小于这个数，那么就可以做一次更新
                f[i] = max(f[i], f[j] + 1);
            }
        }
    }
    // 找整个序列中的最大值
    int res = 1;
    for(int i = 1; i <= n; i ++ ) res = max(res, f[i]);
    cout << res << endl;
    return 0;
}

🪜动态规划 ​

一、背包问题 ​

1.1 01 背包 ​

1.2 完全背包 ​

1.3 多重背包 ​

1.4 分组背包 ​

二、线性 DP ​

2.1 数字三角形 ​

2.2 最长上升子序列 ​