Commita6a1c9a

applewjg

committed

Triangle

Change-Id: I048d685c459bb97fe0ccefcd20d0c3788264804f

1 parentc5edc96 commita6a1c9aCopy full SHA for a6a1c9a

File tree

+35

-0

lines changed

+35

-0

lines changed

Lines changed: 35 additions & 0 deletions

Original file line number	Diff line number	Diff line change
`@@ -0,0 +1,35 @@`
	`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`	`+publicclassSolution {`
	`25`	`+publicintminimumTotal(List<List<Integer>>triangle) {`
	`26`	`+for (inti =triangle.size() -2;i >=0; --i) {`
	`27`	`+List<Integer>cur =triangle.get(i);`
	`28`	`+List<Integer>next =triangle.get(i+1);`
	`29`	`+for (intj =0;j <i +1; ++j) {`
	`30`	`+cur.set(j,Math.min(next.get(j),next.get(j+1)) +cur.get(j));`
	`31`	`+ }`
	`32`	`+ }`
	`33`	`+returntriangle ==null ?0 :triangle.get(0).get(0);`
	`34`	`+ }`
	`35`	`+}`

Comments

(0)