动态规划——数字三角形（百练ID2760）算法

描述

7 38 810 2744 45265(图1)

图1给出了一个数字三角形。从三角形的顶部到底部有很多条不同的路径。对于每条路径，把路径上面的数加起来可以得到一个和，你的任务就是找到最大的和。

注意：路径上的每一步只能从一个数走到下一层上和它最近的左边的那个数或者右边的那个数。输入输入的是一行是一个整数N (1 < N <= 100)，给出三角形的行数。下面的N行给出数字三角形。数字三角形上的数的范围都在0和100之间。输出输出最大的和。样例输入

5 7 3 8 8 1 0 2 7 4 4 4 5 2 6 5

样例输出

30

#include #include using namespace std; int d[101][101]; //输入的是一行是一个整数N (1 < N <= 100) int main() { int n; cin >> n; for (int i = 1; i <= n; ++i) for (int j = 1; j <= i; ++j) cin >> d[i][j]; int *p = d[n]; for (int i = n-1; i>=1; --i) for (int j = 1; j <= i; ++j) p[j] = max(p[j], p[j + 1]) + d[i][j]; cout << p[1] << endl; return 0; }

【动态规划——数字三角形（百练ID2760）】