FilesExpand file tree

 master

/

MinimumPathSum.java

Copy path

BlameMore file actions

BlameMore file actions

Latest commit

 

History

History

History

32 lines (29 loc) · 1012 Bytes

 master

/

MinimumPathSum.java

Top

File metadata and controls

• Code
• Blame

32 lines (29 loc) · 1012 Bytes

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

/*

Author: King, wangjingui@outlook.com

Date: Dec 26, 2014

Problem: Minimum Path Sum

Difficulty: Easy

Source: https://oj.leetcode.com/problems/minimum-path-sum/

Notes:

Given a m x n grid filled with non-negative numbers, find a path from top left to bottom right

which minimizes the sum of all numbers along its path.

Note: You can only move either down or right at any point in time.

Solution: Dynamic Programming. Space O(N).

*/

public class Solution {

public int minPathSum(int[][] grid) {

if (grid.length == 0) return Integer.MIN_VALUE;

int M = grid.length, N = grid[0].length;

int[] dp = new int[N];

dp[0] = grid[0][0];

for (int i = 1; i < N; ++i)

dp[i] = grid[0][i] + dp[i-1];

for (int i = 1; i < M; ++i)

{

dp[0] += grid[i][0];

for (int j = 1; j < N; ++j)

dp[j] = Math.min(dp[j-1], dp[j]) + grid[i][j];

}

return dp[N-1];

}

}