蓝桥杯每日一练——数字三角形（动态规划）

        生活总是让我们遍体鳞伤，但到后来，那些受伤的地方一定会编程我们最强壮的地方。                                                                                                               ——海明威 

P1216 [USACO1.5][IOI1994]数字三角形 Number Triangleshttps://www.luogu.com.cn/problem/P1216

题目描述

观察下面的数字金字塔。

写一个程序来查找从最高点到底部任意处结束的路径，使路径经过数字的和最大。每一步可以走到左下方的点也可以到达右下方的点。

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

在上面的样例中,从 7→3→8→7→5 的路径产生了最大 

思路分析：这道题用搜索的方式从上到下时间复杂度太高，我们可以倒着用dp的思想来做，不断更新父节点的值，更新后的父节点的值应为加上数值较大的孩子的值，具体操作如下：

 c++实现

#includeusing namespace std;int a[1000][1000];int main() {int n;scanf("%d", &n);for (int i = 0; i < n; i++)for (int j = 0; j =0;i--)for (int j = 0; j <=i; j++) {a[i][j] += max(a[i + 1][j], a[i + 1][j + 1]);}cout << a[0][0];return 0;}