于动态规划的启幕之章，借 C++ 笔触绘就算法新篇

注意：代码由易到难

P1216 [IOI 1994] 数字三角形 Number Triangles

题目链接：[IOI 1994] 数字三角形 Number Triangles - 洛谷

题目描述

观察下面的数字金字塔。

写一个程序来查找从最高点到底部任意处结束的路径，使路径经过数字的和最大。每一步可以走到左下方的点也可以到达右下方的点。

在上面的样例中，从 7→3→8→7→57→3→8→7→5 的路径产生了最大权值。

输入格式

第一个行一个正整数 �r ,表示行的数目。

后面每行为这个数字金字塔特定行包含的整数。

输出格式

单独的一行,包含那个可能得到的最大的和。

输入输出样例

输入 #1
5
7
3 8
8 1 0
2 7 4 4
4 5 2 6 5 
输出 #1
30
说明/提示

【数据范围】
对于 100%100% 的数据，1≤r≤1000，所有输入在 [0,100] 范围内。

思路：动态规划，由局部最优达到全局最优

本题属于动态规划中最优子问题类

代码一（dfs+记忆化数组）注意：本代码有一个测试点超时

#include<iostream>  // 包含标准输入输出流库
#include<algorithm> // 包含算法库，用于使用 max 函数
using namespace std;int r; // 全局变量，表示三角形的行数
int arr[1001][1001]; // 用于存储数字三角形的数组，大小为 1001x1001
int memory[1001][1001] = {0}; // 用于记忆化搜索的数组，初始化为 0// 深度优先搜索（DFS）函数，用于计算从 (x, y) 到三角形底部的最大路径和
int dfs(int x, int y) {if (memory[x][y] != 0) return memory[x][y]; // 如果已经计算过 (x, y) 的结果，直接返回int mid;if (x > r || y > x) { // 如果超出三角形范围mid = 0; // 返回 0} else {// 递归计算从 (x, y) 向下和向右下两个方向的最大路径和，并加上当前节点的值mid = max(dfs(x + 1, y), dfs(x + 1, y + 1)) + arr[x][y];}memory[x][y] = mid; // 将结果存储到记忆化数组中return mid; // 返回当前节点的最大路径和
}// 主逻辑函数，读取输入并调用 DFS
void solution() {cin >> r; // 输入三角形的行数for (int i = 1; i <= r; i++) { // 逐行读取三角形的每一行for (int j = 1; j <= i; j++) { // 逐个读取当前行的每个数字cin >> arr[i][j]; // 存储到 arr 数组中}}int maxSum = dfs(1, 1); // 从三角形顶部 (1, 1) 开始计算最大路径和cout << maxSum << endl; // 输出最大路径和
}int main() {ios::sync_with_stdio(false); // 关闭同步，提高输入输出效率cin.tie(nullptr); // 解绑 cin 和 cout，进一步提高效率int T = 1; // 测试用例数量，默认为 1// cin >> T; // 如果需要多个测试用例，可以取消注释while (T--) { // 对每个测试用例调用 solution 函数solution();}return 0; // 程序结束
}

代码二（动态规划，通过）

#include<iostream>
#include<algorithm>
using namespace std;int r; // 三角形的行数
int arr[1002][1002]; // 存储输入的数字三角形
int mid[1002][1002] = {0}; // 动态规划数组，用于存储从底部到当前点的最大路径和// 解决数字三角形问题的函数
void solution()
{cin >> r; // 输入三角形的行数for (int i = 1; i <= r; i++) // 逐行读取三角形的数据{for (int j = 1; j <= i; j++) // 每行的列数等于行号{cin >> arr[i][j]; // 输入当前元素}}// 动态规划从三角形的底部向上计算最大路径和for (int i = r; i >= 1; i--) // 从最后一行开始向上遍历{for (int j = 1; j <= i; j++) // 遍历当前行的每个元素{// 当前点的最大路径和等于当前点的值加上其下方两个点中较大的值mid[i][j] = max(mid[i + 1][j], mid[i + 1][j + 1]) + arr[i][j];}}cout << mid[1][1] << endl; // 输出从顶部到底部的最大路径和
}int main()
{ios::sync_with_stdio(false); // 关闭同步，提高输入输出效率cin.tie(nullptr); // 解绑cin和cout，进一步提高效率int T = 1; // 测试用例数量（这里固定为1）// cin >> T; // 如果需要处理多组数据，可以取消注释while (T--) // 处理每一组数据{solution(); // 调用solution函数解决问题} return 0; // 程序结束
}

代码三（动态规划+滚动数组）

#include<iostream>
#include<algorithm>
#include<cmath>
#include<iomanip>
using namespace std;
#define av(y) setprecision(y)<<fixed;int r; // 三角形的行数
int arr[1002][1002]; // 存储输入的数字三角形
int mid[1002] = {0}; // 动态规划数组，用于存储从底部到当前点的最大路径和（一维数组）// 解决数字三角形问题的函数
void solution()
{cin >> r; // 输入三角形的行数for (int i = 1; i <= r; i++) // 逐行读取三角形的数据{for (int j = 1; j <= i; j++) // 每行的列数等于行号{cin >> arr[i][j]; // 输入当前元素}}// 动态规划从三角形的底部向上计算最大路径和for (int i = r; i >= 1; i--) // 从最后一行开始向上遍历{for (int j = 1; j <= i; j++) // 遍历当前行的每个元素{// 当前点的最大路径和等于当前点的值加上其下方两个点中较大的值// 这里使用一维数组 mid 来存储中间结果mid[j] = max(mid[j], mid[j + 1]) + arr[i][j];}}cout << mid[1] << endl; // 输出从顶部到底部的最大路径和
}int main()
{ios::sync_with_stdio(false); // 关闭同步，提高输入输出效率cin.tie(nullptr); // 解绑cin和cout，进一步提高效率int T = 1; // 测试用例数量（这里固定为1）// cin >> T; // 如果需要处理多组数据，可以取消注释while (T--) // 处理每一组数据{solution(); // 调用solution函数解决问题} return 0; // 程序结束
}

01背包问题

此视频可帮助理解01背包问题：

【自制】01背包问题算法动画讲解_哔哩哔哩_bilibili

有 N 件物品和一个容量是 V 的背包。每件物品只能使用一次。

第 i 件物品的体积是 vi，价值是 wi。

求解将哪些物品装入背包，可使这些物品的总体积不超过背包容量，且总价值最大。
输出最大价值。

输入格式

第一行两个整数N，V，用空格隔开，分别表示物品数量和背包容积。

接下来有 N 行，每行两个整数 vi,wi，用空格隔开，分别表示第 i 件物品的体积和价值。

输出格式

输出一个整数，表示最大价值。

数据范围

0<N,V≤1000
0<vi,wi≤1000

输入样例
4 5
1 2
2 4
3 4
4 5
输出样例：
8

思路：就是每次打算放一个东西时，首先要考虑它放不放得下，放不下的话就直接不放；放得下的话，就要看放他划算还是不放它划算

枚举模拟算法+相对位置

代码一（dfs+记忆化搜索）

#include<iostream>
#include<algorithm>
#include<cmath>
#include<iomanip>
#include<cstring>
using namespace std;
#define av(y) setprecision(y)<<fixed;const int N = 1010; // 定义最大物品数量和背包容量int n, m; // 物品数量和背包容量
int v[N], w[N]; // 物品的体积和价值
int mem[N][N] = {0}; // 记忆化数组，存储已计算的状态// 深度优先搜索 + 记忆化搜索
int dfs(int x, int spV)
{// 如果当前状态已经计算过，直接返回结果if (mem[x][spV]) return mem[x][spV];int sum = 0;// 如果已经考虑完所有物品，返回0if (x < 1){return 0;}// 如果当前背包容量不足以放下第x个物品，只能选择不放if (spV < v[x])  {sum = dfs(x - 1, spV); // 不放当前物品，继续考虑前一个物品}else {// 如果背包容量足够，选择放或不放第x个物品，取两者中的最大值sum = max(dfs(x - 1, spV), dfs(x - 1, spV - v[x]) + w[x]);}// 将当前状态的最优解存储到记忆化数组中mem[x][spV] = sum;return sum;
}void solution()
{cin >> n >> m; // 输入物品数量和背包容量for (int i = 1; i <= n; i++){cin >> v[i] >> w[i]; // 输入每个物品的体积和价值}int res = dfs(n, m); // 从最后一个物品开始，背包容量为mcout << res << endl; // 输出结果
}int main()
{ios::sync_with_stdio(false); // 关闭同步，提高输入输出效率cin.tie(nullptr); // 解绑cin和cout，进一步提高效率int T = 1; // 测试用例数量（这里固定为1）// cin >> T; // 如果需要处理多组数据，可以取消注释while (T--){solution(); // 调用solution函数解决问题} return 0; // 程序结束
}

下面的与上面的代码并无本质区别

#include<iostream>
#include<algorithm>
#include<cmath>
#include<iomanip>
#include<cstring>
using namespace std;
#define av(y) setprecision(y)<<fixed;const int N = 1010;int n, m;
int v[N], w[N];
int mem[N][N];// 深度优先搜索 + 记忆化搜索
int dfs(int x, int spV)
{if (x > n) return 0; // 超过物品数量，返回0if (mem[x][spV] != -1) return mem[x][spV]; // 如果已经计算过，直接返回记忆化的结果int sum = 0;if (spV < v[x])  // 如果当前背包容量不足以放下第x个物品sum = dfs(x + 1, spV); // 不放第x个物品else // 否则，选择放或不放第x个物品，取最大值sum = max(dfs(x + 1, spV), dfs(x + 1, spV - v[x]) + w[x]);mem[x][spV] = sum; // 记忆化结果return sum;
}void solution()
{cin >> n >> m; // 输入物品数量和背包容量for (int i = 1; i <= n; i++){cin >> v[i] >> w[i]; // 输入每个物品的体积和价值}memset(mem, -1, sizeof(mem)); // 初始化记忆化数组为-1int res = dfs(1, m); // 从第1个物品开始，背包容量为mcout << res << endl; // 输出结果
}int main()
{ios::sync_with_stdio(false); // 关闭同步，提高输入输出效率cin.tie(nullptr); // 解绑cin和cout，进一步提高效率int T = 1; // 测试用例数量（这里固定为1）// cin >> T; // 如果需要处理多组数据，可以取消注释while (T--) // 处理每一组数据{solution(); // 调用solution函数解决问题} return 0; // 程序结束
}