导读：前面分享的几道题目，难度都比较大，今天降低下难度，分享一道比较简单的动态规划题。

题目描述：

给定一个三角形，找出自顶向下的最小路径和。每一步只能移动到下一行中相邻的结点上。

例如，给定三角形：

[
 [2],
 [3, 4],
 [6, 5, 7],
[4, 1, 8, 3]
]

自顶向下的最小路径和为 11（即，2 + 3 + 5 + 1 = 11）。

说明：

如果你可以只使用 O(n) 的额外空间（n 为三角形的总行数）来解决这个问题，那么你的算法会很加分。

题目分析：

这个题目，很容易想出一个错误的贪心算法，从顶向下每次选最小的，这么做肯定是错的（虽然这么做能通过题目的样例）！怎么做呢？要求自顶向下的最小路径和，我结合图片来说吧。

先看图片里上面两个方框的转化，假设我们现在从顶部下来后，到达第三层[6 5 7]红色字体的位置，比如在数字6这里，那么我们往第四层走的时候，肯定是选择1，这样才能保证在6这个位置下来后和最小，同理，第三层红色数字5和7，分别选择1和3走到底部！这样原先4层的三角形变成了3层的三角形，问题规模变小了，哈哈！

同理我们也可以把三层的继续变成两层的！见上图下层的方框转化！聪明的读者应该猜到怎么解决这个问题了，没错，从下到上，一层层倒推上去！

根据题意，三角形数字存储在二维数组triangle[][]里面，那么

triangle[i][j] += min(triangle[i + 1][j], triangle[i + 1][j + 1]) ， 0<= i < 三角形层数 - 1

最终的答案就存储在triangle[0][0]里面！给出源码：

复杂度分析：

因为每个三角形的元素遍历了一遍，所以复杂度是和三角形元素相关的，假设三角形n个元素，那复杂度就是O(n)的，空间复杂，因为并没有引入额外空间，所以是O(1)的！leetcode上击败100%的提交。

总结：

虽然题目比较简单，但是麻雀虽小五脏俱全！希望大家有所收获！