首页 > 代码库 > Triangle
Triangle
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).
用DP主要还是要找出递推关系，边界条件
这里的递推关系miniPaht[i][j]表示第i层第j个点的最短路径
miniPath[i][j] = min{miniPath[i - 1][j], miniPath[i - 1][j - 1]} + triangle.get(i).get(j)
注意i和j等于0和等于 triangle.get(i).size - 1的边界条件问题
求出最后一层所有点的最小值，在遍历最后一层找出最小值
参考：http://blog.csdn.net/zhanghaodx082/article/details/24599479
1 public class Solution { 2 public int minimumTotal(List<List<Integer>> triangle) { 3 if(null == triangle) 4 return 0; 5 if(1 == triangle.size()) 6 return triangle.get(0).get(0); 7 int miniPath[][] = new int[triangle.size()][triangle.size()]; 8 for(int i = 0; i < triangle.size(); i++){ 9 for(int j = 0; j < triangle.get(i).size(); j++){10 if(0 == i && 0 == j){11 miniPath[i][j] = triangle.get(0).get(0);12 continue;13 } 14 if(j == 0)15 miniPath[i][j] = miniPath[i - 1][j] + triangle.get(i).get(j);16 else if(j == i)17 miniPath[i][j] = miniPath[i - 1][j - 1] + triangle.get(i).get(j);18 else19 miniPath[i][j] = Math.min(miniPath[i - 1][j], miniPath[i - 1][j - 1]) + triangle.get(i).get(j);20 }21 }22 int ret = miniPath[triangle.size() - 1][0];23 //showMiniPath(miniPath);24 for(int i = 1; i < miniPath[0].length; i++){25 ret = Math.min(ret, miniPath[triangle.size() - 1][i]);26 }27 return ret;28 }29 }
这里可以用原来的空间，使得空间复杂度为O（1）
ps:我没有这么做
Triangle
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。