FilesExpand file tree

 master

/

Triangle120.java

Copy path

Blame

More file actions

Blame

More file actions

Latest commit

 

History

History

History

52 lines (48 loc) · 1.48 KB

 master

/

Triangle120.java

Copy path

Top

File metadata and controls

• Code
• Blame

52 lines (48 loc) · 1.48 KB

Raw

Copy raw file

Download raw file

Open symbols panel

Edit and raw actions

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

/**

* Given a triangle, find the minimum path sum from top to bottom. Each step

* you may move to adjacent numbers on the row below.

*

* For example, given the following triangle

*

* [

* [2],

* [3,4],

* [6,5,7],

* [4,1,8,3]

* ]

* The minimum path sum from top to bottom is 11 (i.e., 2 + 3 + 5 + 1 = 11).

*

* Note:

* Bonus point if you are able to do this using only O(n) extra space, where

* n is the total number of rows in the triangle.

*/

public class Triangle120 {

public int minimumTotal(List<List<Integer>> triangle) {

if (triangle == null || triangle.size() == 0) return 0;

int size = triangle.size();

List<Integer> sums = triangle.get(size - 1);

int i = size - 2;

while (i >= 0) {

List<Integer> curr = triangle.get(i);

int level = curr.size();

for (int j=0; j<level; j++) {

curr.set(j, curr.get(j) + Math.min(sums.get(j), sums.get(j+1)));

}

sums = curr;

i--;

}

return sums.get(0);

}

/**

* https://leetcode.com/problems/triangle/discuss/38724/7-lines-neat-Java-Solution

*/

public int minimumTotal2(List<List<Integer>> triangle) {

int[] A = new int[triangle.size()+1];

for(int i=triangle.size()-1;i>=0;i--){

for(int j=0;j<triangle.get(i).size();j++){

A[j] = Math.min(A[j],A[j+1])+triangle.get(i).get(j);

}

}

return A[0];

}

}