题目：
给定一个数字三角形，找到从顶部到底部的最小路径和。每一步可以移动到下面一行的相邻数字上。
样例
比如，给出下列数字三角形：
[
[2],
[3,4],
[6,5,7],
[4,1,8,3]
]
从顶到底部的最小路径和为11 ( 2 + 3 + 5 + 1 = 11)。
注意
如果你只用额外空间复杂度O(n)的条件下完成可以获得加分，其中n是数字三角形的总行数
解题：
求出从顶点到底部所有节点的路径，在选取最小的路径和.这里给的是下三角矩阵，A[i][j] += Max{A[i-1][j-1],A[i-1][j]}，对应两个边界的情况：A[i][j] += A[i-1][j]、A[i][j] +=A[i-1][j-1]，这样从上向下，在求到最底部时候，找出最小的值。
Java程序：
public class Solution {
/**
* @param triangle: a list of lists of integers.
* @return: An integer, minimum path sum.
*/
public int minimumTotal(int[][] triangle) {
// write your code here
if(triangle.length==1&&triangle[0].length==1)
return triangle[0][0];
int minnum = Integer.MAX_VALUE;
for(int i=1;i<triangle.length;i++){
for(int j=0;j<triangle[i].length;j++){
if(j==0){
triangle[i][j]+=triangle[i-1][j];
}else if(j==triangle[i].length-1){
triangle[i][j]+=triangle[i-1][j-1];
}else{
triangle[i][j]+=Math.min(triangle[i-1][j],triangle[i-1][j-1]);
}
if(i==triangle.length-1)
minnum = Math.min(minnum,triangle[i][j]);
}
}
return minnum;
}
}
总耗时: 2318 ms
Python程序：
class Solution:
"""
@param triangle: a list of lists of integers.
@return: An integer, minimum path sum.
"""
def minimumTotal(self, triangle):
# write your code here if triangle==None:
return 0
if len(triangle)==1 and len(triangle[0])==1:
return triangle[0][0]
minnum = 0
m = len(triangle)
for i in range(1,m):
for j in range(0,len(triangle[i])):
if j==0:
triangle[i][j] += triangle[i-1][j]
elif j==len(triangle[i])-1:
triangle[i][j] += triangle[i-1][j-1]
else:
triangle[i][j] += min(triangle[i-1][j-1],triangle[i-1][j])
if i==len(triangle) - 1 and j==0:
minnum = triangle[i][j]
else:
minnum = min(minnum,triangle[i][j])
return minnum
总耗时: 414 ms
上面是自顶向下的，能否可以自底向上进行,，竟然也可以，这里还不要考虑两个边界的情况，当然上面的其实也可以不考虑的，可以认为是0，这里：triangle[i][j] +=min(triangle[i+1][j] , triangle[i+1][j+1])
Java程序：
public class Solution {
/**
* @param triangle: a list of lists of integers.
* @return: An integer, minimum path sum.
*/
public int minimumTotal(int[][] triangle) {
// write your code here
if(triangle.length==1&&triangle[0].length==1)
return triangle[0][0];
int minnum = Integer.MAX_VALUE;
for(int i=triangle.length-2;i>=0;i--){
for(int j=0;j<triangle[i].length;j++){
triangle[i][j] += Math.min(triangle[i+1][j],triangle[i+1][j+1]);
}
}
minnum = triangle[0][0];
return minnum;
}
}
总耗时: 1384 ms
运行时间也少了好多的
Python程序：
class Solution:
"""
@param triangle: a list of lists of integers.
@return: An integer, minimum path sum.
"""
def minimumTotal(self, triangle):
# write your code here if triangle==None:
return 0
if len(triangle)==1 and len(triangle[0])==1:
return triangle[0][0]
minnum = 0
m = len(triangle)
for i in range(m-2,-1,-1):
for j in range(0,len(triangle[i])):
triangle[i][j] +=min(triangle[i+1][j] , triangle[i+1][j+1])
minnum = triangle[0][0]
return minnum
总耗时: 439 ms