[leetcode] Triangle
Posted November 18, 2013
on:这题其实和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