动态规划

提示

动态规划是记住你之前做过的事

高考时，在枯燥的刷题过程中，经常会遇到一些不太懂的问题，正常的选择是问老师或者同学，然后把它记到错题本上。过了一段时间，如果又遇到了这样的一个问题，而这个问题和上次遇到的很相像。但是呢，已经记不起来了。这时候可以选择翻之前的错题本，或者是再去问老师和同学

闫氏DP分析法

关于其视频讲解教程：bilibili：闫氏DP分析法，从此再也不怕DP问题！

状态表示

想办法将问题的集合表示出来，赐予该集合一个属性。包括但不限于 min max count exist

状态计算

将该集合划分成多个子集合，找到一递推方程表示他们的关系。类似数论的中求组合数的递推公式。

背包问题

01背包问题

问题描述：

有 $N$ 件物品和一个容量式 $M$ 的背包，每件物品只能使用一次。第 $i$ 件物品的体积是 $v_i$ ，价值是 $w_i$ 。求将这些物品装入背包，可使这些物品的总体积不超过背包容量，且总价值最大。

关于状态表示：

设有一数组来代表集合f[t][a] = s，它表示的是，前 $t$ 个物品中（这些物品可以装或不装），当背包容量是 $a$ 时，能装下物品的价值之和的最大值（属性） $s$ 。

关于状态计算：

假设我们正在考虑第 $t$ 个物品，背包容量为 $a$ 的解。它前一个状态有两种表示方式。

选择不装第 $t$ 个物品后，达到了现在的背包容量 $a$ 。

f[t][a] = f[t-1][a]

选择装第 $t$ 个物品后，达到了现在的背包容量 $a$ 。

f[t][a] = f[t-1][a - v[t]] + w[t]

注意：v[t]是物品t的体积，w[t]是物品t的价值，所以f[t-1][a - v[t]]是指前一个集合的状态表示，+ w[t]是计算总价值

ACWING OJ：01背包问题

#include <bits/stdc++.h>

using namespace std;

const int N = 1010;

int n, m;
int v[N], w[N];
// dp[t][a] = s;表示
// 前t个物品中，当背包容量是a时，能装下物品的价值之和的最大值s。
int dp[N][N]; 

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

完全背包问题

问题描述：

有 $N$ 件物品和一个容量式 $M$ 的背包，每件物品可以使用无限次数。第 $i$ 件物品的体积是 $v_i$ ，价值是 $w_i$ 。求将这些物品装入背包，可使这些物品的总体积不超过背包容量，且总价值最大。

关于状态划分

关于状态计算：

假设我们正在考虑第 $t$ 个物品，背包容量为 $a$ 的解。它前一个状态有两种表示方式。

虽然我不是很想写公式，但我看到视频的时候我直呼妙啊～所以我还是写了一大堆公式

对于正在考虑的物品 $t$ ，我们可以选择不装，或者装到反正不超过当前假设背包容量 $a$ 就行。

$f(t, a) = max\{f(t-1, a),f(t-1, a - v_t) + w_t, f(t-1, a-2v_t) + 2w_t , .. , f(t-1, a-kv_t) + kw_t\}$

第 $0$ 项选择不装 $t$ 这件物品： $f(t-1, a)$

第 $1$ 项选择装 $t$ 这件物品 $1$ 件： $f(t-1, a - v_t) + w_t$

第 $2$ 项选择装 $t$ 这件物品 $2$ 件： $f(t-1, a-2v_t) + 2w_t$

第 $k$ 项选择装 $t$ 这件物品 $k$ 件： $f(t-1, a-kv_t) + kw_t$

上面那个公式就是说，从这些项中，在不超过背包容量的前提下，选择一个最大值作为 $f(t, a)$ 的值。

如果说我们用代码写的话，这个公式是不是又需要一个 for 循环？可惜不用，现在开始使用魔法，将 $a$ 换成 $a - v_i$ ，代回上面那个式子。

$f(t, a - v_i) = max\{f(t-1, a - v_t), f(t-1, a-2v_t) + w_t , .. , f(t-1, a-kv_t) + (k-1)w_t\}$

对比上面那个式子，可以发现啊，这个 $f(t, a - v_i)$ 和 $f(t, a)$ 某部分长得很像，只是少加了一个 $w_i$ ，所以最终的递推式子就出来了。

$f(t, a) = max\{f(t-1, a), f(t, a - v_i) + w_i\}$

总结

三个式子写在这，可以找不同对比一下

$f(t, a) = max\{f(t-1, a),f(t-1, a - v_t) + w_t, f(t-1, a-2v_t) + 2w_t , .. , f(t-1, a-kv_t) + kw_t\}$

$f(t, a - v_i) = max\{f(t-1, a - v_t), f(t-1, a-2v_t) + w_t , .. , f(t-1, a-kv_t) + (k-1)w_t\}$

$f(t, a) = max\{f(t-1, a), f(t, a - v_i) + w_i\}$

ACWING OJ：完全背包问题

#include <bits/stdc++.h>

using namespace std;

const int N = 1010;

int n, m;
int v[N], w[N];
// dp[t][a] = s;表示
// 前t个物品中，当背包容量是a时，能装下物品的价值之和的最大值s。
int dp[N][N];

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

线性DP

数字三角形

给定一个如下图所示的数字三角形，从顶部出发，在每一结点可以选择移动至其左下方的结点或移动至其右下方的结点，一直走到底层，要求找出一条路径，使路径上的数字的和最大。（注意，路径上的数字可能有负值）

        7
 8
 1   0
 7   4   4
 5   2   6   5

提示

首先把整个三角形摆成全靠一侧的（如下图所示），然后用一个二位数组a[N][N]去存储每一位的数组

设一数组dp[i][j] = m，代表从起点走到i行j列时路径的最大值m

然后从上往下枚举。现在因为往左靠了，所以对于一个点，它可以从上面或左上角处走过来。

dp[i][j] = max(dp[i-1][j], dp[i-1][j-1]) + a[i][i]

7
 8
 1   0
 7   4   4
 5   2   6   5

#include <bits/stdc++.h>

using namespace std;

const int N = 510, INF = 0x3f3f3f3f;

int a[N][N];
// dp[i][j] = m
// 代表从起点走到i行j列时路径的最大值m
int dp[N][N]; 
int n;

int main (){
    cin >> n;
    for (int i = 1; i <= n; ++ i) {
        for (int j = 1; j <= i; ++ j) {
            cin >> a[i][j];
        }
    }
    
    // 必须要做这两步，如果a[1][1]就是负数，会有很大问题
    // -0x3f3f3f3f是负无穷大
    memset(dp, -0x3f, sizeof dp);
    dp[1][1] = a[1][1];
    
    // 因为第一行已经初始化了，可以直接从第二行2开始
    for (int i = 2; i <= n; ++ i) {
        for (int j = 1; j <= i; ++ j) {
            dp[i][j] = max(dp[i-1][j], dp[i-1][j-1]) + a[i][j];
        }
    }
    
    // 从最后一行的结果中找到一个最大值
    int res = -0x3f3f3f3f;
    for (int i = 1; i <= n; ++ i) {
        res = max(dp[n][i], res);
    }
    cout << res << endl;
     
    return 0;
}

区间DP

合并石子问题

每堆石子有一定的质量，可以用一个整数来描述，现在要将这 $N$ 堆石子合并成为一堆。

每次只能合并相邻的两堆，合并的代价为这两堆石子的质量之和，合并后与这两堆石子相邻的石子将和新堆相邻，合并时由于选择的顺序不同，合并的总代价也不相同。

找出一种合理的方法，使总的代价最小，输出最小代价。

提示

设一数组dp[l][r] = w，代表左端点l到有端点r这个区间内，合并石子的最小代价w。对于每一个dp[l][r] = w，都能在相应区间内，找到一个k，使dp[l][k] + dp[k+1][r]的代价最小。

区间DP的套路：先枚举区间的大小len，然后枚举区间的切分点k。

ACWING OJ：石子合并

#include <bits/stdc++.h>

using namespace std;

const int N = 310;
int n;
int s[N]; // 前缀和数组
// dp[l][r] = w 
// 代表左端点l到有端点r这个区间内，合并石子的最小代价w
int dp[N][N];

int main (){
    cin >> n;
    for (int i = 1; i <= n; ++ i) {
        cin >> s[i];
        s[i] += s[i-1]; //前缀和
    }
    
    // 枚举区间长度
    // 长度为1不需要枚举
    for (int len = 2; len <= n; ++ len) {
        // 枚举左端点
        for (int l = 1; l <= n - len + 1; ++ l) {
            int r = l + len - 1; // 算出右端点
            // 枚举切分点k
            dp[l][r] = 1e8;
            for (int k = l; k <= r; ++ k) {
                int w = s[r] - s[l-1]; // 通过前缀和算出此次合并的代价
                dp[l][r] = min(dp[l][r], + dp[l][k] + dp[k+1][r] + w);
            }
        }
    }
    
    cout << dp[1][n] << endl;
    
    return 0;
}

计数类DP

整数划分

一个正整数 $n$ 可以表示成若干个正整数之和，形如： $n=n_1+n_2+…+n_k$ ，其中 $n_1≥n_2≥…≥n_k,k≥1$ 。

我们将这样的一种表示称为正整数 $n$ 的一种划分。

现在给定一个正整数 $n$ ，请你求出 $n$ 共有多少种不同的划分方法。

提示

转换成可以转化成完全背包问题来做，对于 $n$ ，可看成是物品的数目，也是背包的容量。设有 $n$ 个物品可以选，每个物品的重量为 $1$ 到 $n$ 且每个物品可以用无数次。

#include <bits/stdc++.h>

using namespace std;

const int N = 1010, MOD = 1e9 + 7;
int dp[N][N];
int n;

int main (){
    cin >> n;
    
    for (int i = 1; i <= n; ++ i) {
        dp[i][0] = 1; // 容量为i时，一个物品也不选的方案数为1
    }
    
    for (int i = 1; i <= n; ++ i) {
        for (int j = 1; j <= n; ++ j) {
            dp[i][j] = dp[i-1][j];
            if (j - i >= 0) {
                dp[i][j] = (dp[i - 1][j] + dp[i][j - i]) % MOD;
            }
        }
    }
    
    cout << dp[n][n] << endl;
    
    return 0;
}

记忆化搜索

滑雪

给定一个 $R$ 行 $C$ 列的矩阵，表示一个矩形网格滑雪场。矩阵中第 $i$ 行第 $j$ 列的点表示滑雪场的第 $i$ 行第 $j$ 列区域的高度。一个人从滑雪场中的某个区域内出发，每次可以向上下左右任意一个方向滑动一个单位距离。当然，一个人能够滑动到某相邻区域的前提是该区域的高度低于自己目前所在区域的高度。

下面给出一个矩阵作为例子：

请你找出在该滑雪场中能够完成的最长滑雪轨迹，并输出其长度(可经过最大区域数)。

提示

以递归为例，记忆化搜索就是把搜索的结果保存下来。

进入递归函数后先判断，是否已经搜索过。

如果搜索过，直接返回之前储存过的结果。如果没有搜索过，计算结果后返回且保存下来等待下一次递归函数的调用。

ACWING OJ：滑雪

#include <bits/stdc++.h>

using namespace std;

const int N = 310;

int a[N][N];
int dp[N][N];
int r, c;

int bfs(int x, int y) {
    // 如果搜索过，直接返回结果
    if (dp[x][y] != -1) return dp[x][y];
    // 开始搜索
    int dx[4] = {0, -1, 0, 1}, dy[4] = {1, 0, -1, 0};
    dp[x][y] = 1; //初始化高度为1
    // 枚举四个移动的方向
    for (int i = 0; i < 4; ++ i) {
        // nex, ney是想去的位置
        int nex = x + dx[i], ney = y + dy[i];
        // 如果能滑就滑，选一个最大值存下来
        if (nex >= 1 && nex <= r && ney >= 1 && ney <= c && a[x][y] > a[nex][ney]) {
            dp[x][y] = max(dp[x][y], bfs(nex, ney) + 1);
        } 
    }
    return dp[x][y];
}

int main() {
    cin >> r >> c;
    for (int i = 1; i <= r; ++ i) {
        for (int j = 1; j <= c; ++ j) {
            cin >> a[i][j];
        }
    }
    
    memset(dp, -1, sizeof dp);
    
    int res = 0;
    for (int i = 1; i <= r; ++ i) {
        for (int j = 1; j <= c; ++ j) {
            res = max(res, bfs(i, j));
        }
    }
    
    cout << res << endl;
    
    return 0;
}

提示

背包问题​

01背包问题​

完全背包问题​

总结

线性DP​

数字三角形​

提示

区间DP​

合并石子问题​

提示

计数类DP​

整数划分​

提示

记忆化搜索​

滑雪​

提示