120.Triangle

Posted on | In

Test cases

1
2
3
[[-10]]
[[1],[3,4],[2,3,4]]
[ [2], [3,4], [6,5,7], [4,1,8,3]]

Solution 1: accepted 11ms

DP
Time: O(mn)
Space: O(mn) 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
public int minimumTotal(List<List<Integer>> triangle) {
    for(int i = 1; i < triangle.size(); i++) {
        ArrayList<Integer> row = (ArrayList)triangle.get(i);            
        ArrayList<Integer> lastRow = (ArrayList)triangle.get(i-1);
        for(int j = 0; j < row.size(); j++) {
            if (j == 0) {
                row.set(j, row.get(j) + lastRow.get(0));
            } else if (j == row.size() - 1) {
                row.set(j, row.get(j) + lastRow.get(lastRow.size()-1));
            } else {
                row.set(j, row.get(j) + Math.min(lastRow.get(j-1), lastRow.get(j)));
            }
        }
    }
    int minimum = Integer.MAX_VALUE;
    for(int i: triangle.get(triangle.size()-1)) {
        minimum = Math.min(minimum, i);
    }
    return minimum;
}