109.Triangle
1.Description(Easy)
Given a triangle, find the minimum path sum from top to bottom. Each step you may move to adjacent numbers on the row below.
Notice
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.
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).
2.Code
经典dynamic programming题目
解决方法:
• DFS: Traverse
• DFS: Divide Conquer
• Divide Conquer + Memorization
• Traditional Dynamic Programming
1.Traverse:要用全局变量来记录最优值,超时
2.Divided Conquer--超时
3.记忆化搜索(recursive):Divided Conquer+ Memorization
中间很多点重复计算,去除这些,让程序记录下来结果不要做重复的事,用hash/int[][]

4.DP:时间O(n*n) ,空间 O(n*n)
Bottom up 自底向上(从(x,y)走到bottom),最后返回最上层f[0][0].

Top Down 自顶向下 (从(0,0)走到(x,y) )
public int minimumTotal(int[][] triangle) {
if (triangle == null || triangle.length == 0) {
return -1;
}
if (triangle[0] == null || triangle[0].length == 0) {
return -1;
}
//state:f is the min sum from(x,y) to the bottom
int n=triangle.length;
int[][] f=new int[n][n];
//Initialization:
for(int i=0;i<n;i++){
f[n-1][i]=triangle[n-1][i];
}
//function:
for(int i=n-2;i>=0;i--){
for(int j=i;j>=0;j--){
f[i][j]=Math.min(f[i+1][j],f[i+1][j+1])+triangle[i][j];
}
}
return f[0][0];
}
Last updated
Was this helpful?