Commitbda93ff

applewjg

committed

MinimumPathSum

Change-Id: If5ffcb57ecfdab8d54a0fca6fba7d11dea0e1a76

1 parentf651cef commitbda93ffCopy full SHA for bda93ff

File tree

+32

-0

lines changed

+32

-0

lines changed

Lines changed: 32 additions & 0 deletions

Original file line number	Diff line number	Diff line change
`@@ -0,0 +1,32 @@`
	`1`	`+/*`
	`2`	`+ Author: King, wangjingui@outlook.com`
	`3`	`+ Date: Dec 26, 2014`
	`4`	`+ Problem: Minimum Path Sum`
	`5`	`+ Difficulty: Easy`
	`6`	`+ Source: https://oj.leetcode.com/problems/minimum-path-sum/`
	`7`	`+ Notes:`
	`8`	`+ Given a m x n grid filled with non-negative numbers, find a path from top left to bottom right`
	`9`	`+ which minimizes the sum of all numbers along its path.`
	`10`	`+ Note: You can only move either down or right at any point in time.`
	`11`	`+`
	`12`	`+ Solution: Dynamic Programming. Space O(N).`
	`13`	`+ */`
	`14`	`+publicclassSolution {`
	`15`	`+publicintminPathSum(int[][]grid) {`
	`16`	`+if (grid.length ==0)returnInteger.MIN_VALUE;`
	`17`	`+intM =grid.length,N =grid[0].length;`
	`18`	`+int[]dp =newint[N];`
	`19`	`+dp[0] =grid[0][0];`
	`20`	`+for (inti =1;i <N; ++i)`
	`21`	`+dp[i] =grid[0][i] +dp[i-1];`
	`22`	`+`
	`23`	`+for (inti =1;i <M; ++i)`
	`24`	`+ {`
	`25`	`+dp[0] +=grid[i][0];`
	`26`	`+for (intj =1;j <N; ++j)`
	`27`	`+dp[j] =Math.min(dp[j-1],dp[j]) +grid[i][j];`
	`28`	`+ }`
	`29`	`+`
	`30`	`+returndp[N-1];`
	`31`	`+ }`
	`32`	`+}`

Comments

(0)