LeetCode 120 - Triangle

作者 QIFAN 日期 2017-01-07
LeetCode 120 - Triangle

原题链接: 120. Triangle


题干

给定一个三角数列,求从顶到下最小的路径和。每一步可以移动到下一层相邻的两个节点。

举例

[
[2],
[3,4],
[6,5,7],
[4,1,8,3]
]

最小路径和为 2 + 3 + 5 + 1 = 11

思路

每一步的最小和,都与上一层与其相邻的两个数有关。
假设在第 i 层第 j 个数,上一层的路径和为数组 prevSum
currSum[j] = rowi[j] + min(prevSum[j] + prevSum[j - 1])

头尾要分开计算,因为只有一种路径。

因为只需要用到相邻两层,所以可以用空间 $O(n)$ 。时间复杂度为 $O(n^2)$

代码:

public int minimumTotal(List<List<Integer>> triangle) {
if (triangle.size() == 0) {
return 0;
}
int rowNum = triangle.size();
int[] res = new int[rowNum];
res[0] = triangle.get(0).get(0);
for (int row = 1; row < rowNum; row++) {
// 当前行
List<Integer> currRow = triangle.get(row);
// 计算第一个位置
int prev = res[0];
res[0] = prev + currRow.get(0);
// 中间位置
for (int j = 1; j < row; j++) {
// 上一层中 i - 1 位于 i 位的较小值
int smaller = Math.min(prev, res[j]);
// 保存上一层的 j 位
prev = res[j];
// 计算当层 j 位
res[j] = smaller + currRow.get(j);
}
// 计算最后一个
res[row] = prev + currRow.get(row);
}
// 选取最小值
int min = res[0];
for(int i = 1; i < rowNum; i++) {
min = Math.min(min, res[i]);
}
return min;
}