题目如下

Given a triangle, find the minimum path sum from top to bottom. Each step you may move to adjacent numbers on the row below.
For example, given the following triangle
[
[2],
[3,4],
[6,5,7],
[4,1,8,3]
]

The minimum path sum from top to bottom is 11 (i.e., 2 + 3 + 5 + 1 = 11)
Note:
Bonus point if you are able to do this using only O(n) extra space, where n is the total number of rows in the triangle.

题目大意

给定一个三角形(二维不定长列表)，求出从顶部到底部的最小路径和。每一步你可以选择下一行的两个相邻数字。以上面的三角形为例子：最小路径和是11，路径为2->3->5->1 = 11。如果算法的空间复杂度为O(n)会有额外的得分奖励(n为三角形层数)。

思路

这题使用动态规划较为简便。最初的思路为自顶向下，对每一行进行遍历，同时使用一个一维数组dp存储最佳状态的路径和(dp的长度为三角形的层数)。以此类推，最后一层将会记录所有的路径结果，这时只需要对dp进行遍历求出当中的最小值即可。以上面的三角形为例子。当遍历第一行时，dp的存储为2,0,0,0，第二行时状态为2+3=5,2+4=6，第三行为5+6=11,min(5+5,6+5)=10,6+7=12，第四行为15,min(11+1,10+1)=11,min(10+8,12+8=20)=18,16。只需要遍历最后一行即可求出最小路径和11。

不过在此算法代码编写过程中我发现了两个主要问题，其一因为我们只使用了一维数组，而中间的数字会有来自上一层的两个路径，那么势必会造成数值的丢失，因此需要另外一个变量来存储之前的值，比如在计算第四行dp(1)时，之前的dp(0)已经被更新了，那么就需要有一个临时变量来存储之前的dp(0)=11；其二是时间问题，算法到最后仍然需要对dp进行一次遍历，当层数较多的时候耗费时间较多。

在思考如何解决这两个问题的时候突然想到了二维DP问题的时候空间优化方法，二维DP问题也有数值丢失的问题，而它是使用倒序来解决这个问题的。运用到这个问题时来，我们可以把自顶向下改成自底向上，每次比较该节点两个孩子的数值大小，将小的那个孩子节点的值再加上本身节点的值即为该节点以下的最小路径和，以此类推直到顶点。这两种方式对于结果的正确性来说没有什么影响，这样的话就解决了第一个数值保存的问题，同时我们发现这样也恰好解决了第二个问题，根据此算法，最后的最小路径和肯定会存储在dp(0)，这样就省去了最后对dp的遍历时间。

此算法使用了一个一维数组用于存储结果，空间复杂度为O(n)(n为三角形层数)；同时此算法有两层循环，所以时间复杂度是O(n2)。Java版的代码如下：

1
2
3
4
5
6
7
8
9
public int minimumTotal(List<List<Integer>> triangle) {
    int [] dp = new int[triangle.size() + 1];
    for (int i = triangle.size() - 1; i >= 0; i --){
        for (int j = 0; j < triangle.get(i).size(); j ++){
            dp[j] = triangle.get(i).get(j) + Math.min(dp[j], dp[j + 1]);
        }
    }
    return dp[0];
}

提交结果如下：

提交结果
提交结果

```