Commitc4d9337

committed

1 parent06fd26d commitc4d9337Copy full SHA for c4d9337

File tree

+29

-1

lines changed

+29

-1

lines changed

Lines changed: 29 additions & 1 deletion

Original file line number	Diff line number	Diff line change
`@@ -3,7 +3,10 @@`
`3`	`3`	`importjava.util.List;`
`4`	`4`
`5`	`5`	`publicclassMinimumTotal {`
`6`		`-publicintminimumTotal(List<List<Integer>>triangle) {`
	`6`	`+/*`
	`7`	`+ REC, SOL 1:`
	`8`	`+ */`
	`9`	`+publicintminimumTotal1(List<List<Integer>>triangle) {`
`7`	`10`	`if (triangle ==null \|\|triangle.size() ==0) {`
`8`	`11`	`return0;`
`9`	`12`	`}`
`@@ -34,4 +37,29 @@ public int dfs(List<List<Integer>> triangle, int row, int col, int[][] mem) {`
`34`	`37`
`35`	`38`	`returnmem[row][col];`
`36`	`39`	`}`
	`40`	`+`
	`41`	`+/*`
	`42`	`+ DP, SOL 2:`
	`43`	`+ */`
	`44`	`+publicintminimumTotal(List<List<Integer>>triangle) {`
	`45`	`+if (triangle ==null \|\|triangle.size() ==0) {`
	`46`	`+return0;`
	`47`	`+ }`
	`48`	`+`
	`49`	`+introws =triangle.size();`
	`50`	`+int[]D =newint[rows];`
	`51`	`+`
	`52`	`+for (inti =rows -1;i >=0;i--) {`
	`53`	`+// 注意：边界条件是 j <= i`
	`54`	`+for (intj =0;j <=i;j++) {`
	`55`	`+if (i ==rows -1) {`
	`56`	`+D[j] =triangle.get(i).get(j);`
	`57`	`+ }else {`
	`58`	`+D[j] =triangle.get(i).get(j) +Math.min(D[j],D[j +1]);`
	`59`	`+ }`
	`60`	`+ }`
	`61`	`+ }`
	`62`	`+`
	`63`	`+returnD[0];`
	`64`	`+ }`
`37`	`65`	`}`

Comments

(0)