[leetcode] Triangle
Posted on: November 18, 2013
这题其实和robot一样，每个点取决于从上到自己和从左上角到自己哪个小，但是一变成一维dp就做了好久。主要是因为这个不是取决于头顶和左边了，而是头顶和左上角，于是需要一个临时数组。
public int minimumTotal(ArrayList<ArrayList<Integer>> triangle) {
int res = Integer.MAX_VALUE;
int[] d = new int[triangle.get(triangle.size() - 1).size()];
d[0] = triangle.get(0).get(0);
for (int i = 1; i < triangle.size(); i++) {
int rowSize = triangle.get(i).size();
int[] tmp = new int[rowSize];
for (int j = 0; j < rowSize; j++)
tmp[j] = d[j];
for (int j = 0; j < triangle.get(i).size(); j++) {
int fromAbove = j < rowSize - 1 ? d[j] : Integer.MAX_VALUE;
int fromUpperLeft = j > 0 ? tmp[j - 1] : Integer.MAX_VALUE;
d[j] = Math.min(fromAbove, fromUpperLeft) + triangle.get(i).get(j);
}
}
for (int i = 0; i < d.length; i++) {
res = Math.min(res, d[i]);
}
return res;
}
Tags: 2WayDP
June 12, 2014 at 9:56 am
If you do it in bottom up way, you don’t need a temp array
public int minimumTotal(List<List> triangle) {
int rows = triangle.size();
int lengths = triangle.get(triangle.size()-1).size();
int[] dp = new int[lengths + 1];
for (int i = rows-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];
}
Thank you for your blog, it is very useful