LeetCode 筆記 - 64. Minimum Path Sum

題目在此 64. Minimum Path Sum

給一個 matrix,請計算出從左上到右下最小成本路徑

解題思維

同學,不要猶豫了
還有比這題更 Dynamic programming 的嗎?
用下去吧

程式碼

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
class Solution:
def minPathSum(self, grid: List[List[int]]) -> int:

size_y = len(grid)
size_x = len(grid[0])

if size_x == 1 or size_y == 1:
return sum(map(sum, grid))

dp = [[0 for _ in range(size_x)] for _ in range(size_y)]
dp[0][0] = grid[0][0]

for y in range(size_y):
for x in range(size_x):
if y == 0 and x == 0:
continue
if y == 0:
dp[y][x] = dp[y][x - 1] + grid[y][x]
elif x == 0:
dp[y][x] = dp[y - 1][x] + grid[y][x]
else:
dp[y][x] = min(dp[y - 1][x], dp[y][x - 1]) + grid[y][x]

return dp[size_y - 1][size_x - 1]

也許你也會想看看