难度: Medium
原题链接
https://leetcode.com/problems/minimum-falling-path-sum/description/
内容描述
Given a square array of integers A, we want the minimum sum of a falling path through A.
A falling path starts at any element in the first row, and chooses one element from each row. The next row's choice must be in a column that is different from the previous row's column by at most one.
Example 1:
Input: [[1,2,3],[4,5,6],[7,8,9]]
Output: 12
Explanation:
The possible falling paths are:
[1,4,7], [1,4,8], [1,5,7], [1,5,8], [1,5,9]
[2,4,7], [2,4,8], [2,5,7], [2,5,8], [2,5,9], [2,6,8], [2,6,9]
[3,5,7], [3,5,8], [3,5,9], [3,6,8], [3,6,9]
The falling path with the smallest sum is [1,4,7], so the answer is 12.
Note:
1 <= A.length == A[0].length <= 100
-100 <= A[i][j] <= 100
思路 1 - 时间复杂度: O(row * col^2)- 空间复杂度: O(row * col)******
上来写了个递归，超时，真的蠢。。
class Solution(object):
def minFallingPathSum(self, A):
"""
:type A: List[List[int]]
:rtype: int
"""
def find(A, idx):
if not A or len(A) == 0:
return 0
if idx == 0:
lookup[len(A), idx] = min(A[0][0]+find(A[1:], 0), A[0][1]+find(A[1:], 1))
return lookup[len(A), idx]
elif idx == len(A[0])-1:
lookup[len(A), idx] = min(A[0][-1]+find(A[1:], idx), A[0][-2]+find(A[1:], idx-1))
return lookup[len(A), idx]
else:
lookup[len(A), idx] = min(A[0][idx-1]+find(A[1:],idx-1),A[0][idx]+find(A[1:],idx),A[0][idx+1]+find(A[1:],idx+1))
return lookup[len(A), idx]
res = sys.maxsize
lookup = {}
for idx, num in enumerate(A[0]):
if (len(A[1:]), idx) in lookup:
res = min(res, num+lookup[len(A[1:]), idx])
else:
res = min(res, num+find(A[1:], idx))
return res
思路 2 - 时间复杂度: O(row * col)- 空间复杂度: O(row * col)******
先梳理下要求。 给一个数组，数组从上至下，想找到一条路径 A，这条路径落到最下面的时候的总和是最小的。 每一次下落可选的点是，左边，自身，右边。
[ [1,2,3], [4,5,6], [7,8,9] ]
若从 1 这个点开始，
那么第二次下落可选的点为 [4, 5]，1 是最左边了，没有更左边一位的数了。
第三次若选 4 则可选的点为 [7, 8]，同上。
若选 5 则可选的点为 [7, 8, 9] 左 中 右。
-
一开始可能想到的是贪心的，只能从最上面开始下落，那一开始就选最小的，然后不断选最小的不就可以了吗？ 对于所有的情况，贪心往往得到的是次优解，而不是最优解。
-
能想到贪心，进一步可以先到动态规划（DP）。 对于每一个点来说，要想保证它是当前最小的，那么就需要在它上面的 左 中 右 三个点里找到一个最小的值给自己。
从下至上我们来看，4 可以选择的点为 [1, 2]，那么它要想保证加上一个值最小，要选的只能是 1 。 5 则可以选的点为 [1, 2, 3]，也是 1。 6 可以是 [2, 3]，那么是 3。
这一层的子问题解决完之后变成了 [5(4+1), 6(5+1), 8(6+2)]。
在开始下一层，7 是 [5, 6] 里选择。 8 是 [5, 6, 7] 里选择。
class Solution(object):
def minFallingPathSum(self, A):
"""
:type A: List[List[int]]
:rtype: int
"""
if not A or len(A) == 0 or len(A[0]) == 0:
return 0
row = len(A)
col = len(A[0]) if row else 0
dp = [[0] * col for i in range(row)]
dp[0] = A[0]
for i in range(1, row):
for j in range(col):
if j == 0:
dp[i][j] = min(dp[i-1][0], dp[i-1][1]) + A[i][j]
elif j == col-1:
dp[i][j] = min(dp[i-1][-1], dp[i-1][-2]) + A[i][j]
else:
dp[i][j] = min(dp[i-1][j-1], dp[i-1][j], dp[i-1][j+1]) + A[i][j]
return min(dp[-1])思路 3 - 时间复杂度: O(row * col)- 空间复杂度: O(1)******
可以写的更加简洁巧妙一些, 优化空间到O(1)
class Solution(object):
def minFallingPathSum(self, A):
"""
:type A: List[List[int]]
:rtype: int
"""
for i in range(1, len(A)):
for j in range(len(A[0])):
prev_left = A[i-1][j-1] if j-1 >= 0 else float('inf')
prev_right = A[i-1][j+1] if j+1 < len(A[0]) else float('inf')
A[i][j] += min(A[i-1][j], prev_left, prev_right)
return min(A[-1])