Given a triangle, find the minimum path sum from top to bottom. Each step you may move to adjacent numbers on the row below.
Example
For example, given the following triangle
[
[2],
[3,4],
[6,5,7],
[4,1,8,3]
]
The minimum path sum from top to bottom is 11 (i.e., 2 + 3 + 5 + 1 = 11).
Note
Bonus point if you are able to do this using only O(n) extra space, where n is the total number of rows in the triangle.
Version 1. Up-Bottom
想法直白 但是做起来麻烦 要考虑很多边界条件 不推荐
//f[i][j] = Math.min(f[i-1][j-1], f[i-1][j])+grid[i][j]
public int minimumTotal(ArrayList<ArrayList<Integer>> triangle) {
//O(n^2) space
//f[i][j] = Math.min(f[i-1][j-1], f[i-1][j])+grid[i][j]
if (triangle == null || triangle.size() == 0) {
return 0;
}
int size = triangle.size();
int[][] resultMap = new int[size][size];
resultMap[0][0] = triangle.get(0).get(0);
for (int i = 1; i < size; i++) {
ArrayList<Integer> curr = triangle.get(i);
for (int j = 0; j < curr.size(); j++) {
if (j == 0) {
resultMap[i][j] = resultMap[i - 1][j] + curr.get(j);
} else {
if (j < triangle.get(i - 1).size()) {
resultMap[i][j] = Math.min(resultMap[i - 1][j - 1], resultMap[i - 1][j]) + curr.get(j);
} else {
resultMap[i][j] = resultMap[i - 1][j - 1] + curr.get(j);
}
}
}
}
int min = Integer.MAX_VALUE;
for (int i = 0; i < size; i++) {
if (resultMap[size - 1][i] < min) {
min = resultMap[size - 1][i];
}
}
return min;
}
Version 2. Bottom-Up O(n^2) space
可以想成求从底部任一点出发到左上角的最小路径和 代码简洁 不会outOfBound
public int minimumTotal(ArrayList < ArrayList < Integer >> triangle) {
if (triangle == null || triangle.size() == 0) {
return 0;
}
int size = triangle.size();
int[][] resultMap = new int[size][size];
//init the last row
ArrayList < Integer > lastRow = triangle.get(size - 1);
for (int i = 0; i < size; i++) {
resultMap[size - 1][i] = lastRow.get(i);
}
//from bottom to top
for (int i = size - 2; i >= 0; i--) {
ArrayList < Integer > curr = triangle.get(i);
for (int j = 0; j < curr.size(); j++) {
resultMap[i][j] = Math.min(resultMap[i + 1][j], resultMap[i + 1][j + 1]) + curr.get(j);
}
}
return resultMap[0][0];
}
Version 3. Bottom-Up O(n) space
在Version 2的基础上 只用2*n的数组记录数据
代码不变 只需要行数mod 2 (modulus %) 就行了
public int minimumTotal(ArrayList < ArrayList < Integer >> triangle) {
if (triangle == null || triangle.size() == 0) {
return 0;
}
int size = triangle.size();
int[][] resultMap = new int[2][size];
//init the last row
ArrayList < Integer > lastRow = triangle.get(size - 1);
for (int i = 0; i < size; i++) {
resultMap[(size - 1) % 2][i] = lastRow.get(i);
}
//from bottom to top
for (int i = size - 2; i >= 0; i--) {
ArrayList < Integer > curr = triangle.get(i);
for (int j = 0; j < curr.size(); j++) {
resultMap[i % 2][j] = Math.min(resultMap[(i + 1) % 2][j], resultMap[(i + 1) % 2][j + 1]) + curr.get(j);
}
}
return resultMap[0][0];
}
