Posted on 2022-12-13 16:41
Uriel 閱讀(47)
評論(0) 編輯 收藏 引用 所屬分類:
DP 、
閑來無事重切Leet Code
給定一個2D矩陣，從第一行往下走，每次可以向左、向右，或者再同一列，每個格子有一個值，問從上走到下，經過的格子之和最小多少，裸DP，轉移方程
dp[i][j] = min(dp[i][j], dp[i - 1][j - 1] + matrix[i][j], dp[i - 1][j + 1] + matrix[i][j])
因為每一行的狀態只和上一行有關，所以DP不用開二維，用另一個變量暫存上一行的狀態即可
1 #931
2 #Runtime: 171 ms (Beats70.25%)
3 #Memory: 14.5 MB (Beats27.22%)
4
5 class Solution(object):
6 def minFallingPathSum(self, matrix):
7 """
8 :type matrix: List[List[int]]
9 :rtype: int
10 """
11 dp_pre = matrix[0]
12 dp = [20000] * len(matrix[0])
13 for i in range(1, len(matrix)):
14 for j in range(len(matrix[0])):
15 if j > 0:
16 dp[j] = min(dp[j], dp_pre[j - 1] + matrix[i][j])
17 if j < len(matrix[0]) - 1:
18 dp[j] = min(dp[j], dp_pre[j + 1] + matrix[i][j])
19 dp[j] = min(dp[j], dp_pre[j] + matrix[i][j])
20 dp_pre = dp
21 dp = [20000] * len(matrix[0])
22 return min(dp_pre)