forked from algorithm009-class01/algorithm009-class01
-
Notifications
You must be signed in to change notification settings - Fork 0
Expand file tree
/
Copy pathMinimumTotal.java
More file actions
49 lines (46 loc) · 1.46 KB
/
MinimumTotal.java
File metadata and controls
49 lines (46 loc) · 1.46 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
package dynamic;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;
public class MinimumTotal {
public int minimumTotal(List<List<Integer>> triangel){
if (triangel == null || triangel.size() == 0){
return 0;
}
int rowNum = triangel.size();
int[] dp = new int[rowNum];
for (int i = 0; i < triangel.get(rowNum - 1).size(); i++) {
dp[i] = triangel.get(rowNum - 1).get(i);
}
for (int row = rowNum -2;row >=0;row--){
for (int col = 0;col <= row;col++){
dp[col] = Math.min(dp[col],dp[col+1]) + triangel.get(row).get(col);
}
}
return dp[0];
}
public static void main(String[] args) {
List<Integer> list1 = new ArrayList<>();
list1.add(1);
List<Integer> list2 = new ArrayList<>();
list2.add(3);
list2.add(4);
List<Integer> list3 = new ArrayList<>();
list3.add(6);
list3.add(5);
list3.add(7);
List<Integer> list4 = new ArrayList<>();
list4.add(4);
list4.add(1);
list4.add(8);
list4.add(3);
List<List<Integer>> triangels = new ArrayList<>();
triangels.add(list1);
triangels.add(list2);
triangels.add(list3);
triangels.add(list4);
MinimumTotal minimumTotal = new MinimumTotal();
int r = minimumTotal.minimumTotal(triangels);
System.out.println(r);
}
}