题目：https://www.luogu.org/problemnew/show/P1216
题意：
给定一个三角形。从顶走到底，问路径上的数字之和最大是多少。
走的时候可以往左下（实际上纵坐标不变）或是往右下（纵坐标+1）
思路：
用$dp[i][j]$表示从$（1，1）$走到$（i，j）$的最大值。
$（i，j）$可以从$（i-1，j）$或是$（i-1，j-1）$走过来
所以$dp[i][j] = max(dp[i-1][j], dp[i-1][j-1]) + num[i][j]$
初态为$dp[1][1] = num[1][1]$，最后遍历一次第$n$行的$dp$值
1 #include<stdio.h> 2 #include<stdlib.h> 3 #include<map> 4 #include<set> 5 #include<iostream> 6 #include<cstring> 7 #include<algorithm> 8 #include<vector> 9 #include<cmath> 10 #include<queue> 11 12 #define inf 0x7f7f7f7f 13 using namespace std; 14 typedef long long LL; 15 typedef pair<int, int> pr; 16 17 const int maxn = 1005; 18 int n; 19 int tri[maxn][maxn]; 20 int dp[maxn][maxn]; 21 22 int main() 23 { 24 scanf("%d", &n); 25 for(int i = 1; i <= n; i++){ 26 for(int j = 1; j <= i; j++){ 27 scanf("%d", &tri[i][j]); 28 } 29 } 30 dp[1][1] = tri[1][1]; 31 for(int i = 2; i <= n; i++){ 32 for(int j = 1; j <= i; j++){ 33 dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - 1]) + tri[i][j]; 34 } 35 } 36 37 int ans = 0; 38 for(int i = 1; i <= n; i++){ 39 ans = max(ans, dp[n][i]); 40 } 41 printf("%d\n", ans); 42 return 0; 43 }
原文：https://www.cnblogs.com/wyboooo/p/10384997.html