120 Triangle
120. Triangle
1. Question
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
[
[2],
[3,4],
[6,5,7],
[4,1,8,3]
]
The minimum path sum from top to bottom is11
(i.e., 2+3+5+1= 11).
Note:
Bonus point if you are able to do this using onlyO(n) extra space, where_n_is the total number of rows in the triangle.
2. Implementation
(1) DP
思路: 根据题目三角形的特性,我们可以知道最底下的行的列数等于三角形的行数,dp[i][j]表示在第i行和第j列的最小path sum, dp[i][j] = triagnle.get(i).get(j) + Math.min(dp[i + 1][j], dp[i + 1][j + 1])
class Solution {
public int minimumTotal(List<List<Integer>> triangle) {
if (triangle == null || triangle.size() == 0) {
return 0;
}
int n = triangle.size();
int[][] dp = new int[n][n];
for (int j = 0; j < triangle.get(n - 1).size(); j++) {
dp[n - 1][j] = triangle.get(n - 1).get(j);
}
for (int i = n - 2; i >= 0; i--) {
for (int j = 0; j < triangle.get(i).size(); j++) {
dp[i][j] = triangle.get(i).get(j) + Math.min(dp[i + 1][j], dp[i + 1][j + 1]);
}
}
return dp[0][0];
}
}
3. Time & Space Complexity
DP: 时间复杂度O(n^2), 空间复杂度O(n^2)
Last updated
Was this helpful?