给定一个由n行数字组成的数字三角形如下图所示。试设计一个算法，计算出从三角形的顶至底的一条路径，使该路径经过的数字总和最大。 
对于给定的由n行数字组成的数字三角形，计算从三角形的顶至底的路径经过的数字和的最大值。
输入数据的第1行是数字三角形的行数n，1≤n≤100。接下来n行是数字三角形各行中的数字。所有数字在0..99之间。
输出数据只有一个整数，表示计算出的最大值。
5 7 3 8 8 1 0 2 7 4 4 4 5 2 6 5
1.dp:
1 #include <bits/stdc++.h> 2 3 using namespace std; 4 5 int a[105][105], dp[105][105]; // dp数组表示从(i,j)开始出发的最大和 6 7 int main() { 8 int n, res; 9 cin >> n; 10 11 for(int i = 1; i <= n; i++) { 12 for(int j = 1; j <= i; j++) { 13 cin >> a[i][j]; 14 } 15 } 16 for(int j = 1; j <= n; j++) dp[n][j] = a[n][j]; 17 for(int i = n-1; i >= 1; i--) { // 注意i是逆序的 18 for(int j = 1; j <= n; j++) 19 dp[i][j] = a[i][j] + max(dp[i+1][j], dp[i+1][j+1]); 20 } 21 cout << dp[1][1]; 22 return 0; 23 }
2.记忆化搜索:
1 #include <bits/stdc++.h> 2 3 using namespace std; 4 5 int n, res; 6 int a[105][105], dp[105][105]; 7 8 int solve(int i, int j) { 9 if(dp[i][j] >= 0) return dp[i][j]; // 大于0说明已经求过该点.减少重复 10 return dp[i][j] = a[i][j] + (i == n ? 0 : max(solve(i+1, j), solve(i+1, j+1))); // 注意判断边界 11 } 12 13 int main() { 14 15 cin >> n; 16 memset(dp, -1, sizeof(dp)); // 初始全赋为-1,方便后面判断 17 for(int i = 1; i <= n; i++) { 18 for(int j = 1; j <= i; j++) { 19 cin >> a[i][j]; 20 } 21 } 22 23 cout << solve(1, 1); // 从第一排第一个数开始出发的最大和 24 return 0; 25 }
原文：https://www.cnblogs.com/knightoflake/p/14465928.html