Posted on 2022-12-13 16:41
Uriel 阅读(33)
评论(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)