leetcode 931. Minimum Falling Path Sum（python）_python题falling

描述

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.
1
2
3
4
5
6
7
8

Note:

1 <= A.length == A[0].length <= 100
-100 <= A[i][j] <= 100
1
2

解析

根据题意，设置一个二位列表 dp，数组中每个位置都要从上一层获得三个相邻列的最小值，然后和自身相加，然后遍历完成之后，得到 dp 最后一行的最大值即可，时间复杂度为 O(MN)，空间复杂度为 O(MN)。

解答

class Solution(object):
    def minFallingPathSum(self, A):
        """
        :type A: List[List[int]]
        :rtype: int
        """
        M, N = len(A), len(A[0])
        dp = [[0] * (N + 2) for _ in range(M)]
        for i in range(M):
            dp[i][0] = dp[i][-1] = float('inf')
            for j in range(1, N + 1):
                dp[i][j] = A[i][j - 1]
        for i in range(1, M):
            for j in range(1, N + 1):
                dp[i][j] = A[i][j - 1] + min(dp[i - 1][j - 1], dp[i - 1][j], dp[i - 1][j + 1])
        return min(dp[-1])
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

运行结果

Runtime: 92 ms, faster than 92.42% of Python online submissions for Minimum Falling Path Sum.
Memory Usage: 12.2 MB, less than 72.73% of Python online submissions for Minimum Falling Path Sum.
1
2

解析

根据题意，只要一个一维数组 dp 就可以完成二维数组的任务，思路和上面的一样，只不过每次都是在一维的 dp 中不断覆盖之前的值，遍历完成之后得到 dp 的最大值即可，时间复杂度为 O(MN)，空间复杂度为 O(MN)。

解答

class Solution(object):
    def minFallingPathSum(self, A):
        """
        :type A: List[List[int]]
        :rtype: int
        """
    dp = A[0]
    for a in A[1:]: 
        dp = [ value+min(dp[c], dp[max(c-1,0)], dp[min(len(A[0])-1,c+1)] ) for c,value in enumerate(a)]
    return min(dp)
1
2
3
4
5
6
7
8
9
10

运行结果

Runtime: 96 ms, faster than 82.58% of Python online submissions for Minimum Falling Path Sum.
Memory Usage: 12.4 MB, less than 20.13% of Python online submissions for Minimum Falling Path Sum.
1
2

每日格言：常常是最终一把钥匙打开了门。