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 , , ,
] The minimum path sum from top to bottom is 11 (i.e., 2 + 3 + 5 + 1 = 11).
我们用动态规划来解决,从下往上开始相加,例如题目中的例子,最后一行是,我们每次从中选取相邻两个元素中较小的那个与它上面序列对应的元素相加, 4和1我们选取1,然后与6相加,1和8我们选取1与5相加,这样一直更新到最上面的一行,就是我们要找的结果。代码如下:
public class Solution {
public int minimumTotal(List<List<Integer>> triangle) {
if(triangle == null) return 0;
for(int i = triangle.size() - 1; i > 0; i--) {
for(int j = 0; j < triangle.get(i - 1).size(); j++) {
triangle.get(i - 1).set(j, Math.min(triangle.get(i).get(j), triangle.get(i).get(j + 1)) + triangle.get(i - 1).get(j));
}
}
return triangle.get(0).get(0);
}
}
上面的代码没有什么问题,可以顺利AC,空间复杂度为O(1)。但是它改变了原有的数据,如果题目要求我们不能改变原有的数据,我们可以借助一个数组来完成。代码如下:
public class Solution {
public int minimumTotal(List<List<Integer>> triangle) {
if(triangle == null) return 0;
int[] dp = new int[triangle.size() + 1];
for(int i = triangle.size() - 1; i >= 0; i--) {
for(int j = 0; j < triangle.get(i).size(); j++) {
dp[j] = triangle.get(i).get(j) + Math.min(dp[j], dp[j + 1]);
}
}
return dp[0];
}
}