0120. Triangle - kumaeki/LeetCode GitHub Wiki
Given a triangle array, return the minimum path sum from top to bottom.
For each step, you may move to an adjacent number of the row below. More formally, if you are on index i on the current row, you may move to either index i or index i + 1 on the next row.
Example 1:
Input: triangle = [[2],[3,4],[6,5,7],[4,1,8,3]]
Output: 11
Explanation: The triangle looks like:
2
3 4
6 5 7
4 1 8 3
The minimum path sum from top to bottom is 2 + 3 + 5 + 1 = 11 (underlined above).
Example 2:
Input: triangle = [[-10]]
Output: -10
Constraints:
- 1 <= triangle.length <= 200
- triangle[0].length == 1
- triangle[i].length == triangle[i - 1].length + 1
- -104 <= triangle[i][j] <= 104
注意到每个位置的值基本都是根据上一层左右位置的中较小的那个值计算而来.
(这里用"基本"是因为有例外情况, 第一行的值是直接得到,其他行最左侧和最右侧的值只相关于上一层的最左侧和最右侧的值)
仍然是Dynamic Programming, 定义两个数组, 分别存储前一次计算结果和当前计算结果.
然后循环往复,直到计算到最后一行,得到结果.
class Solution {
public int minimumTotal(List<List<Integer>> triangle) {
int n = triangle.size();
// 定义两个数组来储存计算结果
int[] pre = new int[n], cur = new int[n];
// 第一行只有一个数,比较特殊, 单独赋值
pre[0] = triangle.get(0).get(0);
// 从第二行开始
for(int i = 1; i < n; i++){
// 当前行
List<Integer> list = triangle.get(i);
// 根据移动规则, 最左侧的值是确定的,每一行最左侧的值相加
cur[0] = pre[0] + list.get(0);
// 根据移动规则, 最右侧的值是确定的,每一行最右侧的值相加
cur[i] = pre[i - 1] + list.get(i);
// 中间的值,是在上一层左右之间选较小的值
for(int j = 1; j < i; j++){
cur[j] = Math.min(pre[j - 1], pre[j]) + list.get(j);
}
// 计算结果放入pre
pre = cur;
// 重置cur
cur = new int[n];
}
// 找到最小值
int res = Integer.MAX_VALUE;
for(int v : pre)
res = Math.min(res, v);
return res;
}
}