1+ /*
2+ Author: Andy, nkuwjg@gmail.com
3+ Date: May 14, 2013
4+ Problem: Triangle
5+ Difficulty: Easy
6+ Source: https://oj.leetcode.com/problems/triangle/
7+ Notes:
8+ Given a triangle, find the minimum path sum from top to bottom. Each step you may move to adjacent numbers on the row below.
9+ For example, given the following triangle
10+ [
11+ [2],
12+ [3,4],
13+ [6,5,7],
14+ [4,1,8,3]
15+ ]
16+ The minimum path sum from top to bottom is 11 (i.e., 2 + 3 + 5 + 1 = 11).
17+ Note:
18+ Bonus point if you are able to do this using only O(n) extra space, where n is the total number
19+ of rows in the triangle.
20+
21+ Solution: Note that there are n elements in the n-th row (n starts from 1).
22+ 1. DP. Do not need additional spaces (happen in-place).
23+ */
24+ public class Solution {
25+ public int minimumTotal (List <List <Integer >>triangle ) {
26+ for (int i =triangle .size () -2 ;i >=0 ; --i ) {
27+ List <Integer >cur =triangle .get (i );
28+ List <Integer >next =triangle .get (i +1 );
29+ for (int j =0 ;j <i +1 ; ++j ) {
30+ cur .set (j ,Math .min (next .get (j ),next .get (j +1 )) +cur .get (j ));
31+ }
32+ }
33+ return triangle ==null ?0 :triangle .get (0 ).get (0 );
34+ }
35+ }
