注意：代码由易到难
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; // 程序结束
}
