120. 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).
方法
实际上这道题是关于树结构的动态规划的一道经典题型并非DFS。
对于树从top->bottom，或者从bottom->top,实际上两者可以相互转换。对于本题为top->bottom，实际上计算时从从bottom->top。
假设x和y是k的孩子节点，如果从x到底部和从y到底部的最少路径和已知，那么从k的开始的最少路径和也可以得到。状态转换方程如下,k为第k行，minpath表示第k行第i列的最少路径，所以根节点的最短路径就是minpath[0][0]：
minpath[k][i] = min( minpath[k+1][i], minpath[k+1][i+1]) + triangle[k][i]
public class Solution {
public int minimumTotal(List<List<Integer>> triangle) {
int size = triangle.size();
int si = triangle.get(size-1).size();
int[][] s = new int[size][si];
for(int i = 0; i < si; i++){
s[size-1][i] = triangle.get(size-1).get(i);
}
for(int i = size-2; i >= 0; i--){
for(int j = 0; j < triangle.get(i).size(); j++){
s[i][j] = Math.min(s[i+1][j],s[i+1][j+1]) + triangle.get(i).get(j);
}
}
return s[0][0];
}
}