导读：前面分享的几道题目，难度都比较大，今天降低下难度，分享一道比较简单的动态规划题。
题目描述：
给定一个三角形，找出自顶向下的最小路径和。每一步只能移动到下一行中相邻的结点上。
例如，给定三角形：
[ [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%的提交。
总结：
虽然题目比较简单，但是麻雀虽小五脏俱全！希望大家有所收获！
