1. 题目：
给定一个三角形，找出自顶向下的最小路径和。每一步只能移动到下一行中相邻的结点上。
例如，给定三角形：
[
[2],
[3,4],
[6,5,7],
[4,1,8,3]
]自顶向下的最小路径和为 11（即，2 + 3 + 5 + 1 = 11）。
说明：
如果你可以只使用 O(n) 的额外空间（n 为三角形的总行数）来解决这个问题，那么你的算法会很加分。
2. 解题思路
从第一层到最后一层，每层中元素[i, j]的相邻父元素为[i -1, j - 1]与[i -1, j ],
参考图论中的Dijkstra算法，采取从顶点开始向外搜索，计算到达各节点的最短路径的方法；
由于题目中的图（树？）每层间都是单向的，所以不必每次循环更新所有节点的最短路径，只需从顶层开始逐层计算从顶点到各节点的最短距离，并直接更新到该节点，最后从最底层取出值最小的元素即为题解：
3. 代码 JAVA
class Solution {
public int minimumTotal(List<List<Integer>> triangle) {
int i = 0, j = 0;// 循环变量（为节省空间所以单独定义）
int pe, af;// 暂存父节点值
// 逐层计算最短路径，第一层不必计算
for (i = 1; i < triangle.size(); i++) {
// 每行第一个元素只有一个父元素
triangle.get(i).set(0, triangle.get(i - 1).get(0) + triangle.get(i).get(0));
for (j = 1; j < i; j++) {
pe = triangle.get(i - 1).get(j);
af = triangle.get(i - 1).get(j - 1);
if (pe < af)// 将较小的父元素加到当前节点，更新最短路径
triangle.get(i).set(j, pe + triangle.get(i).get(j));
else
triangle.get(i).set(j, af + triangle.get(i).get(j));
}
// 每行最后一个元素只有一个父元素
triangle.get(i).set(i, triangle.get(i - 1).get(i - 1) + triangle.get(i).get(i));
}
// 取出最后一层中最小的路径
return Collections.min(triangle.get(triangle.size() - 1));
}
}最优提交结果：
执行用时 : 7 ms, 在Triangle的Java提交中击败了53.31% 的用户
内存消耗 : 35.1 MB, 在Triangle的Java提交中击败了96.99% 的用户
*****
*****
之后每次重新提交结果都不一样，不知道为啥
4. 复杂度
我自认为空间复杂度为 O(1)
时间复杂度：O(n^2)
内容来源于网络如有侵权请私信删除
- 还没有人评论，欢迎说说您的想法！
客服
