-
Notifications
You must be signed in to change notification settings - Fork 3
/
minSumPathTria.java
33 lines (23 loc) · 962 Bytes
/
minSumPathTria.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
28
29
30
31
32
33
import java.util.*;
public class minSumPathTria {
//Given a triangle, find the minimum path sum from top to bottom. Each step you may move to adjacent
//numbers on the row below.
public int minimumTotal(ArrayList<ArrayList<Integer>> a) {
int T[] = new int[a.size()];
for (int i = 0; i < a.get(a.size() -1).size(); i++)
T[i] = a.get(a.size() -1).get(i);
for (int i = a.size() -2; i >= 0; i--){
for (int j = 0; j < a.get(i +1).size() -1; j++)
T[j] = a.get(i).get(j) + Math.min(T[j], T[j + 1]);
}
return T[0];
}
public static void main(String[] args) {
ArrayList<ArrayList<Integer>> arrayList = new ArrayList<>();
arrayList.add(new ArrayList<>(Arrays.asList(2)));
arrayList.add(new ArrayList<>(Arrays.asList(3, 4)));
arrayList.add(new ArrayList<>(Arrays.asList(6, 5, 7)));
arrayList.add(new ArrayList<>(Arrays.asList(4, 14, 20, 1)));
System.out.println(new minSumPathTria().minimumTotal(arrayList));
}
}