1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
|
public class Triangle {
public int minimumTotal(List<List<Integer>> triangle) {
if (triangle == null || triangle.isEmpty()) {
return 0;
}
int size = triangle.size();
int[] result = new int[size];
for (int i = 0; i < size; i++) {
result[i] = triangle.get(size - 1).get(i);
}
for (int i = triangle.size() - 2; i >= 0; i--) {
int s = triangle.get(i).size();
for (int j = 0; j < s; j++) {
result[j] = triangle.get(i).get(j) + Math.min(result[j], result[j + 1]);
}
}
return result[0];
}
}
|