FilesExpand file tree

 master

/

solution2.py

Copy path

Blame

More file actions

Blame

More file actions

Latest commit

 

History

History

History

25 lines (24 loc) · 913 Bytes

 master

/

solution2.py

Copy path

Top

File metadata and controls

• Code
• Blame

25 lines (24 loc) · 913 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

class Solution:

# @param grid, a list of lists of integers

# @return an integer

def minPathSum(self, grid):

n = len(grid)

m = len(grid[0])

t = [[-1 for i in range(m)] for j in range(n)]

return self.min_path_sum_aux(grid, m - 1, n - 1, t)

def min_path_sum_aux(self, grid, x, y, t):

if x == 0 and y == 0:

return grid[y][x]

elif t[y][x] != -1:

return t[y][x]

elif x == 0 and y > 0:

t[y][x] = grid[y][x] + self.min_path_sum_aux(grid, x, y - 1, t)

return t[y][x]

elif x > 0 and y == 0:

t[y][x] = grid[y][x] + self.min_path_sum_aux(grid, x - 1, y, t)

return t[y][x]

else:

a = self.min_path_sum_aux(grid, x - 1, y, t)

b = self.min_path_sum_aux(grid, x, y - 1, t)

t[y][x] = grid[y][x] + min(a, b)

return t[y][x]