Difficulty:: Medium
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
1
2
3
4
5
6
| [
[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.
Solution
Language: Java
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
| class Solution {
public int minimumTotal(List<List<Integer>> triangle) {
if (triangle == null || triangle.size() == 0) {
return -1;
}
int m = triangle.size();
int n = triangle.get(m - 1).size();
int[][] dp = new int[m][n];
for (int i = 0; i < m; i++) {
Arrays.fill(dp[i], Integer.MAX_VALUE);
}
return divideConquer(triangle, dp, 0, 0);
}
public int divideConquer(List<List<Integer>> triangle, int[][] dp, int x, int y) {
if (x >= dp.length || y >= dp[x].length) {
return 0;
}
if (dp[x][y] != Integer.MAX_VALUE) {
return dp[x][y];
}
dp[x][y] = triangle.get(x).get(y) +
Math.min(divideConquer(triangle, dp, x + 1, y),
divideConquer(triangle, dp, x + 1, y + 1));
return dp[x][y];
}
}
|
直接使用DP
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
| class Solution {
public int minimumTotal(List<List<Integer>> triangle) {
if (triangle == null || triangle.size() == 0) {
return -1;
}
int m = triangle.size();
int[][] dp = new int[m][m];
for (int i = 0; i < m; i++) {
dp[m - 1][i] = triangle.get(m - 1).get(i);
}
for (int i = m - 2; i >= 0; i--) {
for (int j = 0; j <= i; j++) {
dp[i][j] = triangle.get(i).get(j) + Math.min(dp[i + 1][j], dp[i + 1][j + 1]);
}
}
return dp[0][0];
}
}
|
DP O(n)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
| class Solution {
public int minimumTotal(List<List<Integer>> triangle) {
if (triangle == null || triangle.size() == 0) {
return 0;
}
int[][] dp = new int[2][triangle.size()];
dp[0][0] = triangle.get(0).get(0);
for (int i = 1; i < triangle.size(); i++) {
for (int j = 0; j < triangle.get(i).size(); j++) {
if (j == 0) {
dp[i % 2][j] = dp[(i - 1) % 2][j] + triangle.get(i).get(j);
} else if (j == triangle.get(i).size() - 1) {
dp[i % 2][j] = dp[(i - 1) % 2][j - 1] + triangle.get(i).get(j);
} else {
dp[i % 2][j] = triangle.get(i).get(j) + Math.min(dp[(i - 1) % 2][j], dp[(i - 1) % 2][j - 1]);
}
}
}
int[] leaf = dp[(triangle.size() - 1) % 2];
int min = Integer.MAX_VALUE;
for (int n : leaf) {
if (n < min) {
min = n;
}
}
return min;
}
}
|