【题目来源】
AcWing：898. 数字三角形 - AcWing题库
【题目描述】
给定一个如下图所示的数字三角形，从顶部出发，在每一结点可以选择移动至其左下方的结点或移动至其右下方的结点，一直走到底层，要求找出一条路径，使路径上的数字的和最大。
73 88 1 02 7 4 4
4 5 2 6 5
【输入】
第一行包含整数 ，表示数字三角形的层数。
接下来 \(n\) 行，每行包含若干整数，其中第 \(i\) 行表示数字三角形第 \(i\) 层包含的整数。
【输出】
输出一个整数，表示最大的路径数字和。
【输入样例】
5
7
3 8
8 1 0
2 7 4 4
4 5 2 6 5
【输出样例】
30
【解题思路】
【算法标签】
《AcWing 898 数字三角形》 #动态规划# #线性DP#
【代码详解】
#include <bits/stdc++.h>
using namespace std;const int N = 510, INF = 1e9; // 三角形的层数最大500，INF表示无穷大int w[N][N]; // w[i][j]存储三角形的值
int n; // 三角形的层数
int f[N][N]; // f[i][j]表示从(1,1)走到(i,j)的最大路径和int main()
{// 初始化数组memset(w, 0, sizeof(w));// 读入三角形的层数cin >> n;// 读入三角形的数值for (int i = 1; i <= n; i++){for (int j = 1; j <= i; j++){cin >> w[i][j];}}// 因为有负数，初始化f数组为负无穷// 注意：三角形的边界也需要初始化for (int i = 0; i <= n; i++){for (int j = 0; j <= i + 1; j++) // 注意边界：三角形外多初始化一圈{f[i][j] = -INF;}}// 初始化起点f[1][1] = w[1][1];// 动态规划计算每个位置的最大路径和for (int i = 2; i <= n; i++) // 从第2层开始{for (int j = 1; j <= i; j++) // 第i层有i个位置{// 状态转移方程：// 从左上角(f[i-1][j-1])或正上方(f[i-1][j])走到当前位置f[i][j] = max(f[i-1][j-1], f[i-1][j]) + w[i][j];}}// 在最后一行中寻找最大路径和int ans = -INF;for (int i = 1; i <= n; i++){ans = max(ans, f[n][i]);}cout << ans;return 0;
}
//从下往上
#include <bits/stdc++.h>
using namespace std;const int N = 510, INF = 1e9; // 三角形的层数最大500，INF表示无穷大int w[N][N]; // w[i][j]存储三角形的值
int n; // 三角形的层数
int f[N][N]; // f[i][j]表示从(i,j)走到最底层的最大路径和int main()
{// 注意：这里memset的使用有误// memset(w, 0, sizeof(0)); // sizeof(0)应该是sizeof(w)// 应该改为：memset(w, 0, sizeof(w));// 读入三角形的层数cin >> n;// 读入三角形的数值for (int i = 1; i <= n; i++){for (int j = 1; j <= i; j++){cin >> w[i][j];}}// 自底向上动态规划// 1. 初始化最后一行for (int i = 1; i <= n; i++){f[n][i] = w[n][i]; // 最后一行到底部的路径就是自身}// 2. 从倒数第二行开始向上递推for (int i = n - 1; i >= 1; i--) // 从下往上{for (int j = 1; j <= i; j++) // 第i行有i个位置{// 状态转移方程：// 从当前位置(i,j)可以走到下一行的左下方(i+1,j)或右下方(i+1,j+1)f[i][j] = max(f[i+1][j+1], f[i+1][j]) + w[i][j];}}// 输出结果：从顶部到底部的最大路径和cout << f[1][1];return 0;
}
【运行结果】
5
7
3 8
8 1 0
2 7 4 4
4 5 2 6 5
30