120. Triangle

https://leetcode.com/problems/triangle/description/

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).

今天仔细分析了HashMap，又理清了推荐系统的思路，很有成就感，我发现还是需要专注的，心无旁骛地分析一件事情才能很快做出来。

对于这道题，跟那个Pascal's三角的排列差不多，我们要把他左对齐的话就容易找规律了。
[
[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).

这道题如果没有 Each step you may move to adjacent numbers on the row below这个条件的话就是简单的找最小值就行了，多了这个条件就成了动态规划。我对动态规划的印象是，类似Paths那道题，空间换时间。也就是把目前为止所有格子的minimum path计算出来。

这道题的状态转移方程我试着写一下：
paths[i][j] = nums[i][j] + min{paths[i-1][j-1], paths[i-1][j]}

这方程的前提是掐头去尾。
花了半小时写代码，调试了好几次才AC..不过我感觉自己有点懂动归了。

public class Solution {
    public int minimumTotal(List<List<Integer>> triangle) {
        //第一列和最后一列的path sum
        for (int i = 1; i < triangle.size(); i++) {
            triangle.get(i).set(0, triangle.get(i - 1).get(0) + triangle.get(i).get(0));
            int cell_size = triangle.get(i).size();
            triangle.get(i).set(cell_size - 1, triangle.get(i - 1).get(cell_size - 2) + triangle.get(i).get(cell_size - 1));
        }

        //第三行开始
        for (int i = 2; i < triangle.size(); i++)
            //每一行的第二个数到倒数第二个数
            for (int j = 1; j < triangle.get(i).size() - 1; j++) {
                triangle.get(i).set(j, triangle.get(i).get(j) + Math.min(triangle.get(i - 1).get(j - 1), triangle.get(i - 1).get(j)));
            }
        //min要定义成最后一行第一个数
        int min = triangle.get(triangle.size() - 1).get(0);
        for (int i = 0; i < triangle.get(triangle.size() - 1).size(); i++) {
            if (min > triangle.get(triangle.size() - 1).get(i))
                min = triangle.get(triangle.size() - 1).get(i);
        }
        return min;
    }
}

写的过程中犯的几个错误：

        triangle.get(i).set(cell_size - 1, triangle.get(i - 1).get(cell_size - 2) + triangle.get(i).get(cell_size - 1));

cell_size - 2写成了size-1。

           triangle.get(i).set(j, triangle.get(i).get(j) + Math.min(triangle.get(i - 1).get(j - 1), triangle.get(i - 1).get(j)));

状态转移方程忘了加上triangle.get(i).get(j)了。。

把 int min = triangle.get(triangle.size() - 1).get(0);初始化成了Integer.MIN_VALUE.

120. Triangle

推荐阅读更多精彩内容