【DP】931. Minimum Falling Path Sum

echobingo

发布于 2019-06-02 15:16:19

3260

发布于 2019-06-02 15:16:19

题目描述：

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

解题思路：

这道题是求最小下降路径和，即位置 (row, col) 可以到达位置 (row+1, col-1)、(row+1, col)、(row+1, col+1) 。

很明显这是一道动态规划的题目。用 dp[row][col] 表示到达位置 (row, col) 的最小累计和，它的计算等于当前位置 A[row][col] 加上 (row-1, col-1)、(row-1, col) 和 (row-1, col+1) 这三个位置的最小值，即： dp[row][col] = A[row][col] + min(dp[row-1][col-1], dp[row-1][col], dp[row-1][col+1]) 因此，我们只需要从上到下遍历方阵，更新每个位置的累加最小值。最后，dp 最后一行的最小值就是最终的答案。

注意：在编程的时候要初始化第一行 dp[0] = A[0]，同时在遍历每一行时要注意最左和最右位置的边界条件。

Python3 实现：

class Solution:
    def minFallingPathSum(self, A: List[List[int]]) -> int:
        lens = len(A)
        dp = [[0] * lens for _ in range(lens)]
        dp[0] = A[0]  # 初始化第一行
        for row in range(1, lens):
            dp[row][0] = A[row][0] + min(dp[row-1][0], dp[row-1][1])
            for col in range(1, lens-1):
                dp[row][col] = A[row][col] + min(dp[row-1][col-1], dp[row-1][col], dp[row-1][col+1])
            dp[row][lens-1] = A[row][lens-1] + min(dp[row-1][lens-2], dp[row-1][lens-1])
        return min(dp[-1])

本文参与腾讯云自媒体同步曝光计划，分享自作者个人站点/博客。

原始发表：2019.06.01 ，如有侵权请联系 cloudcommunity@tencent.com 删除

编程算法

本文分享自作者个人站点/博客前往查看

如有侵权，请联系 cloudcommunity@tencent.com 删除。

本文参与腾讯云自媒体同步曝光计划，欢迎热爱写作的你一起参与！

编程算法

登录后参与评论

0 条评论

热度