前言
✨本博客讲解 蓝桥杯C/C++ 备赛所涉及算法知识，此博客为第六讲：简单dp【例题】
本篇博客所包含习题有：
👊01背包问题
👊摘花生
👊最长上升子序列
简单dp【习题】见博客：蓝桥杯第六讲–简单dp【习题】
博客内容以题代讲，通过讲解题目的做法来帮助读者快速理解算法内容，需要注意：学习算法不能光过脑，更要实践，请读者务必自己敲写一遍本博客相关代码！！！
01背包问题
题目要求
题目描述：
输入格式：
输出格式：
输出一个整数，表示最大价值。
数据范围：
输入样例：
4 5
1 2
2 4
3 4
4 5
输出样例：
8
思路分析
朴素版
上图其实已经说的很详细了，用文字去解释就是我们定义的状态：f[i][j]，就是表示从前 i 个物品里面进行选择，选择的总体积不超过 j 的最大值，我们的状态转移方程推导：对于第 i 个商品，我们有两种决策：选它或者不选它，如果不选择它，对应此时的状态就是 f[i−1][j]，如果选择它，对应此时的状态就是 f[i−1][j−v[i]]+w[i]，每次决策都取两者的最大值。
优化
通过朴素版的分析，可以明白：对于第一位状态，我们其实只会用到它的上一维状态去进行优化，如我们在计算 f [ i ] [ j ] 的时候，只会用到 f [ i − 1 ] ，对于f[i−2] 这种状态我们是不会使用的，所以我们可以把第一维给去掉，那么代码1：
for (int i = 1; i <= n; i ++ ) for (int j = 0; j <= m; j ++ ) { f[i][j] = f[i - 1][j]; if (v[i] <= j) f[i][j] = max(f[i][j], f[i - 1][j - v[i]] + w[i]); }
就会变成代码2：
for (int i = 1; i <= n; i ++ ) for (int j = 0; j <= m; j ++ ) { f[j] = f[j]; if (v[i] <= j) f[j] = max(f[j], f[j - v[i]] + w[i]); }
我们观察到：f[j] = f[j];是一个恒等式，故可以删掉，变成代码3：
for (int i = 1; i <= n; i ++ ) for (int j = 0; j <= m; j ++ ) { if (v[i] <= j) f[j] = max(f[j], f[j - v[i]] + w[i]); }
代码（朴素版）
#include <iostream> #include <cstring> #include <algorithm> const int N = 1010; int v[N], w[N]; int f[N][N]; using namespace std; 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 = 0; j <= m; j ++ ) { f[i][j] = f[i - 1][j]; if (v[i] <= j) f[i][j] = max(f[i][j], f[i - 1][j - v[i]] + w[i]); } cout << f[n][m] << endl; return 0; }
代码（优化）
#include <iostream> #include <cstring> #include <algorithm> const int N = 1010; int v[N], w[N]; int f[N]; using namespace std; 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 = m; j >= v[i]; j -- ) f[j] = max(f[j], f[j - v[i]] + w[i]); cout << f[m] << endl; return 0; }
摘花生
题目要求
题目描述：
Hello Kitty 想摘点花生送给她喜欢的米老鼠。
她来到一片有网格状道路的矩形花生地(如下图)，从西北角进去，东南角出来。
地里每个道路的交叉点上都有种着一株花生苗，上面有若干颗花生，经过一株花生苗就能摘走该它上面所有的花生。
Hello Kitty 只能向东或向南走，不能向西或向北走。
问 Hello Kitty 最多能够摘到多少颗花生。
输入格式：
输出格式：
对每组输入数据，输出一行，内容为 Hello Kitty 能摘到得最多的花生颗数。
数据范围：
输入样例：
2
2 2
1 1
3 4
2 3
2 3 4
1 6 5
输出样例：
8
16
思路分析
代码
#include <iostream> #include <algorithm> using namespace std; const int N = 110; int w[N][N]; int f[N][N]; int main() { int t; cin >> t; while (t -- ) { int r, c; cin >> r >> c; for (int i = 1; i <= r; i ++ ) for (int j = 1; j <= c; j ++ ) cin >> w[i][j]; for (int i = 1; i <= r; i ++ ) for (int j = 1; j <= c; j ++ ) f[i][j] = max(f[i - 1][j], f[i][j - 1]) + w[i][j]; cout << f[r][c] << endl; } return 0; }
最长上升子序列
题目要求
题目描述：
给定一个长度为 N的数列，求数值严格单调递增的子序列的长度最长是多少。
输入格式：
输出格式：
输出一个整数，表示最大长度。
数据范围：
输入样例：
7
3 1 2 1 8 5 6
输出样例：
4
思路分析
代码
#include <iostream> #include <cstring> #include <algorithm> using namespace std; const int N = 1010; int a[N]; int f[N]; int main() { int n; cin >> n; for (int i = 1; i <= n; i ++ ) cin >> a[i]; for (int i = 1; i <= n; i ++ ) { f[i] = 1; for (int j = 1; j < i; j ++ ) if (a[j] < a[i]) f[i] = max(f[i], f[j] + 1); } int res = 0; for (int i = 1; i <= n; i ++ ) res = max(res, f[i]); cout << res << endl; return 0; }
