-
Notifications
You must be signed in to change notification settings - Fork 0
/
Copy path0064-minimum_path_sum.py
51 lines (45 loc) · 1.7 KB
/
0064-minimum_path_sum.py
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
45
46
47
48
49
50
51
## Just do a forward fill, for each position total up cost to neighors, track minimum cost
## Becareful of edge cases where ncol == 1 or nrow == 1
class Solution:
def minPathSum(self, grid: List[List[int]]) -> int:
nrows = len(grid)
ncols = len(grid[0])
if nrows == ncols == 1:
return grid[0][0]
if nrows == 1:
return sum(grid[0])
if ncols == 1:
return sum([r[0] for r in grid])
cost = []
for n in range(nrows):
cost.append([float('inf')] * ncols)
cost[0][0] = grid[0][0]
for r in range(len(grid)):
for c in range(len(grid[r])):
self.visit(grid, cost, r, c)
return cost[-1][-1]
def visit(self, grid, cost, r, c):
nrows = len(grid)
ncols = len(grid[0])
neighbors = self.getNeighbors(r,c, nrows, ncols)
print(neighbors)
for n_r, n_c in neighbors:
cost[n_r][n_c] = min(cost[n_r][n_c], cost[r][c] + grid[n_r][n_c])
def getNeighbors(self, r, c, nrows, ncols):
if r == 0 and c == 0:
return [(r+1, c), (r, c+1)]
if r == 0 and c == ncols - 1:
return [(r+1, c), (r, c-1)]
if r == nrows - 1 and c == 0:
return [(r-1, c), (r, c+1)]
if r == nrows - 1 and c == ncols - 1:
return [(r-1, c), (r, c-1)]
if r == 0:
return [(r+1, c), (r, c-1), (r, c+1)]
if r == nrows - 1:
return [(r-1, c), (r, c-1), (r, c+1)]
if c == 0:
return [(r+1, c), (r-1, c), (r, c+1)]
if c == ncols - 1:
return [(r+1, c), (r-1, c), (r, c-1)]
return [(r+1, c), (r-1, c), (r, c+1), (r, c-1)]