FilesExpand file tree

 master

/

MinimumPathSum.cs

Copy path

Blame

More file actions

Blame

More file actions

Latest commit

 

History

History

History

executable file

·

45 lines (41 loc) · 2.89 KB

 master

/

MinimumPathSum.cs

Copy path

Top

File metadata and controls

• Code
• Blame

executable file

·

45 lines (41 loc) · 2.89 KB

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

33

34

35

36

37

38

39

40

41

42

43

44

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

// Author : codeyu

// Date : Sunday, December 11, 2016 4:11:41 PM

/**********************************************************************************

*

* 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.

*

**********************************************************************************/

using System;

using System.Collections.Generic;

using Algorithms.Utils;

namespace Algorithms

{

public class Solution064

{

public static int MinPathSum(int[,] grid)

{

if(grid == null || grid.GetLength(0) == 0|| grid.GetLength(1)==0)

return 0;

int[] res = new int[grid.GetLength(1)];

res[0] = grid[0,0];

for(int i=1;i<grid.GetLength(1);i++)

{

res[i] = res[i-1]+grid[0,i];

}

for(int i=1;i<grid.GetLength(0);i++)

{

for(int j=0;j<grid.GetLength(1);j++)

{

if(j==0)

res[j] += grid[i,j];

else

res[j] = Math.Min(res[j-1], res[j])+grid[i,j];

}

}

return res[grid.GetLength(1)-1];

}

}

}