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.
题目标签：Array, Dynamic Programming
题目给了我们一个三角的array list， 让我们从中找到最小值的路线。一旦看到这种每一个点可以选择路线的，有不同可能性的，大多都是 DP 问题。一开始自己写了一个 复制一个 三角的array list， 然后从上到下的遍历，把每一个种可能都存到新的三角 array list。但是用了过多的 extra space， 没有满足它的要求。 所以通过后发现速度太慢，想了一会就放弃了，去网上找答案。有时候如果认认真真自己想一道这样类似的题目，可能会用3，4个小时的时间，而且，还不一定想的出正确答案，所以通常花费1个多小时的话，就果断去找答案了。
只用O(n) 空间的方法：
设立一个 n+1 array，然后从最下面一行倒着遍历回第一行，对于n+1 array里面的数字，取它和它后面 两者之中 小的那一个数字，加上 在三角里相对应位置的数字， 存入n+1 array。 基本思想是，利用倒着遍历的方法，可以把每一个数字的最优选择path 存入n+1 array里，当遍历回第一行的时候，因为只有一个数字，那么取得的path 一定是最优的那一个，换句话说，就是minimum path sum。
举例： 1 5 3 2 为最优路线
4 8 对于每一个数字，选下面相邻2个中小的那一个 + 自己 一直遍历回第一行
0 0 0 0 0 设立的1d array 相当于在这个位置
设立n + 1 array: 从三角最下面遍历回最上面， 每次在1d array 里 取相邻两个种小的那一个 + 三角里对应位置的数字
0 0 0 0 0 初始为0，为什么要多一个呢，因为每次都是取当前和后面一个数字比较，所以当遍历到第四个的时候，需要和第五个比较
遍历三角开始， 结合上面三角图形来看
4 1 8 3 0 遍历三角4183 -> 因为1d array里都是0，所以每次取相邻里小的那一个的话，都是0 + 三角里对应位置的数字，相当于 把最后一行复制一下
7 6 10 3 0 遍历三角657 -> 从之前存的里面，挑对应相邻两个中小的那个 + 自己 存入1d array
9 10 10 3 0 遍历三角34
11 10 10 3 0 遍历三角2 -> 得到答案11
Java Solution:
Runtime beats 58.69%
完成日期：08/27/2017
关键词：Array, Dynamic Programming
关键点：从下向上遍历，把最优路线存入1d array
class Solution
{
public int minimumTotal(List<List<Integer>> triangle)
{
// create a k+1 size array
int [] arr = new int[triangle.size() + 1]; // iterate from last row to first row
for(int i=triangle.size()-1; i>=0; i--)
{
// iterate each row from left to right
for(int j=0; j<triangle.get(i).size(); j++)
{
arr[j] = Math.min(arr[j], arr[j+1]) + triangle.get(i).get(j);
}
} /* the answer is the first number because we start from last row back to first row
and first row is just one number */
return arr[0];
}
}
参考资料：
https://discuss.leetcode.com/topic/22254/7-lines-neat-java-solution
LeetCode 算法题目列表 - LeetCode Algorithms Questions List