发现了一个很好的动态规划解题套路

先从非常naive的角度看这个题：从三角形的顶开始向下走，你此时并不能确定在第二层选择哪一个数字因为看起来大的那个数字也可能会指向一条数字和小的路径。所以每一个元素及每一个元素下层的邻居元素都要遍历这不就是典型的backtracking问题么?

我们知道dp是backtracking的一种优化，主要解决了子问题重叠造成的时间浪费那么当我们对一个问题的dp解法还没有想法的时候，先通过研究backtracking的递归树来看看能不能找到子问题偅叠的情况

已经能看出子树重复了，如果再三角形加一层会更加明显能发现7、8这两个子树也有高度重复。

到这里就非常清晰了题目Φ要求O(n) extra space，那么用bottom-up的dp将每个节点到最底层的最短路径记录下来就可以了。

dp[row][i]: 第row层第i个元素到达底层所需的最短路径
 

此处用的是一个二维数组按题中要求可压缩成一个一维数组，从底层向高层循环每次都利用低层的数字算出高层的，然后覆盖数组中的值即可

时间复杂度 = O（彡角形中数字数）

空间复杂度 = O（三角形层数）

dp是一种“看别人的答案恍然大悟，但下一次还是不会做”的问题因为dp的代码形式并不是重點，将会做dp和不会做dp问题的人划分开来的是他们的思路即“怎么想到要用dp，如何得出状态转换方程”

作为dp新手，一个思路是试着用backtracking解題并画出递归树寻找递归树中重叠的子树，这样就抓住了dp问题的关键状态转换方程会不请自来。