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).
今天仔細(xì)分析了HashMap，又理清了推薦系統(tǒng)的思路，很有成就感，我發(fā)現(xiàn)還是需要專注的，心無(wú)旁騖地分析一件事情才能很快做出來(lái)。
對(duì)于這道題，跟那個(gè)Pascal's三角的排列差不多，我們要把他左對(duì)齊的話就容易找規(guī)律了。
[
[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).
這道題如果沒(méi)有 Each step you may move to adjacent numbers on the row below這個(gè)條件的話就是簡(jiǎn)單的找最小值就行了，多了這個(gè)條件就成了動(dòng)態(tài)規(guī)劃。我對(duì)動(dòng)態(tài)規(guī)劃的印象是，類似Paths那道題，空間換時(shí)間。也就是把目前為止所有格子的minimum path計(jì)算出來(lái)。
這道題的狀態(tài)轉(zhuǎn)移方程我試著寫一下：
paths[i][j] = nums[i][j] + min{paths[i-1][j-1], paths[i-1][j]}
這方程的前提是掐頭去尾。
花了半小時(shí)寫代碼，調(diào)試了好幾次才AC..不過(guò)我感覺自己有點(diǎn)懂動(dòng)歸了。
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++)
//每一行的第二個(gè)數(shù)到倒數(shù)第二個(gè)數(shù)
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要定義成最后一行第一個(gè)數(shù)
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;
}
}
寫的過(guò)程中犯的幾個(gè)錯(cuò)誤：
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)));
狀態(tài)轉(zhuǎn)移方程忘了加上triangle.get(i).get(j)了。。
- 把 int min = triangle.get(triangle.size() - 1).get(0);初始化成了Integer.MIN_VALUE.
