給定一個(gè)2D矩陣，從第一行往下走，每次可以向左、向右，或者再同一列，每個(gè)格子有一個(gè)值，問(wèn)從上走到下，經(jīng)過(guò)的格子之和最小多少，裸DP，轉(zhuǎn)移方程
dp[i][j] = min(dp[i][j], dp[i - 1][j - 1] + matrix[i][j], dp[i - 1][j + 1] + matrix[i][j])
因?yàn)槊恳恍械臓顟B(tài)只和上一行有關(guān)，所以DP不用開(kāi)二維，用另一個(gè)變量暫存上一行的狀態(tài)即可
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)