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.
