⚠️ 舊文提醒：本文發佈於約 4 年前，部分內容或指令可能已過時，請斟酌參考。
題目在此 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]
|
也許你也會想看看