如何运用动态规划算法解决数字三角形问题？

本文共计674个文字，预计阅读时间需要3分钟。

题目：数字三角形+题目介绍：如图所示的数字三角形，要求从上方顶点开始一步一步下降到底部，每一步必须下降一层，求出经过的所有数字的最大和。

输入：第一行输入一个整数n，代表n行数字三角形；第二行开始，每行输入n个数字，代表三角形的一行数字。

输出：经过的所有数字的最大和。

题目：数字三角形

题目介绍：如图所示的数字三角形，要求从最上方顶点开始一步一步下到最底层，每一步必须下一层，求出所经过的数字的最大和。

输入：第一行值n，代表n行数值；后面的n行数据代表每一行的数字。

输出：经过数字的最大和。

例：

输入：

4

1

3 2

4 10 1

4 3 2 20

输出：

24

分析：这也是一个典型的贪心算法无法解决的问题，同样可以用动态规划（dp算法）来解决。把边界数字首先初始化到结果矩阵中，再根据状态方程完成结果矩阵的遍历。需要注意的就是数组不是矩形而是三角形，与传统的状态方程相比需要做点改进。