forked from huailian123/Leetcode-java
-
Notifications
You must be signed in to change notification settings - Fork 0
Expand file tree
/
Copy path109_minimumTotal.java
More file actions
65 lines (54 loc) · 1.77 KB
/
Copy path109_minimumTotal.java
File metadata and controls
65 lines (54 loc) · 1.77 KB
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
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
//Top to Bottom
//1607ms
public class Solution {
/**
* @param triangle: a list of lists of integers.
* @return: An integer, minimum path sum.
*/
public int minimumTotal(int[][] triangle) {
// write your code here
if(triangle == null || triangle.length == 0) return 0;
if(triangle[0] == null || triangle[0].length == 0) return 0;
int m = triangle.length;
int[][] dp = new int[m][m];
dp[0][0] = triangle[0][0];
for(int i = 1; i < m; i++){
dp[i][0] = dp[i-1][0]+triangle[i][0];
dp[i][i] = dp[i-1][i-1]+triangle[i][i];
}
for(int i = 1; i < m; i++){
for(int j = 1; j < i; j++){
dp[i][j] = Math.min(dp[i-1][j-1], dp[i-1][j])+triangle[i][j];
}
}
int res = dp[m-1][0];
for(int i = 1; i < m; i++){
res = Math.min(res, dp[m-1][i]);
}
return res;
}
}
//Bottom to Top
//1629ms
public class Solution {
/**
* @param triangle: a list of lists of integers.
* @return: An integer, minimum path sum.
*/
public int minimumTotal(int[][] triangle) {
// write your code here
if(triangle == null || triangle.length == 0) return 0;
if(triangle[0] == null || triangle[0].length == 0) return 0;
int m = triangle.length;
int[][] dp = new int[m][m];
for(int i = 0; i < m; i++){
dp[m-1][i] = triangle[m-1][i];
}
for(int i = m-2; i>= 0; i--){
for(int j = 0; j<= i; j++){ // be careful this is j<= i
dp[i][j] = triangle[i][j]+Math.min(dp[i+1][j],dp[i+1][j+1]);
}
}
return dp[0][0];
}
}