leetcode: Triangle

问题描述：

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.

原问题链接：https://leetcode.com/problems/triangle/

 

问题分析

　　这个问题要找到合理的思路还是有点麻烦的。对于前面问题的描述中，我们需要看这么一个规律。给定的第几行，那么这一行就有几个元素。而这里还有一个要求就是对于上面一行的元素来说，它可以和它下一行同一个索引位置以及一个相邻位置的元素相加。所以对于前一行第i个位置的元素来说，它可以和下一行里的i - 1, i, i + 1位置的元素选择相加。对于每个相加后有重叠位置的元素，我们取更小的那个元素设置为它们相加后选的值。

　　按照这个思路，我们在实现的时候，每次要创建一个比前一行长度大一的数组，然后通过比较每个元素和它周边的值来求的下一行的值。这个值将作为计算下一行值的基础。就这样一直到最后一行。我们最后从得到的数组里找出最小的那个元素。这个思路虽然可行，但是我们的空间使用情况超出了O(n)的限制。因为每次加一的申请空间，我们的空间使用情况甚至达到了0(n x n)的情况。

　　看来，我们要寻找新的思路。在上面的思路里，我们之所以申请的空间超出了限制，是因为每次没法重用前面依次申请的数组。因为每次要创建的数组长度要加一。如果我们一开始就创建一个长度为n的数组的话，我们需要控制每一次它遍历所能访问的长度限制。这样会比较麻烦。

　　不过如果我们转换一下思路，比如说，我们从最后一行开始向上面一行每次这么比较累加的话呢？我们可以申请一个和最后一行长度一样的数组，把最后一行的值赋给这个数组。而要求它上一行数组元素的时候，我们可以得到一个这样的关系：

minLen[i] = Math.min(minLen[i], minLen[i + 1]) + triangle.get(layer).get(i)。其中layer表示当前所在的层。这种不断收缩的方式可以使得代码更加简洁。我们最终返回的结果里只需要返回minLen[0]就可以了。

　　这样，我们可以得到详细的实现代码如下：

 

public class Solution {
    public int minimumTotal(List<List<Integer>> triangle) {
        int n = triangle.size();
        int[] minLen = new int[n];
        for(int i = 0; i < triangle.get(n - 1).size(); i++)
            minLen[i] = triangle.get(n - 1).get(i);
        for(int layer = n - 2; layer >= 0; layer--) {
            for(int i = 0; i <= layer; i++) {
                minLen[i] = Math.min(minLen[i], minLen[i + 1]) + triangle.get(layer).get(i);
            }
        }
        return minLen[0];
    }
}