前往小程序,Get更优阅读体验!
立即前往
首页
学习
活动
专区
工具
TVP
发布
社区首页 >专栏 >【DP】931. Minimum Falling Path Sum

【DP】931. Minimum Falling Path Sum

作者头像
echobingo
发布2019-06-02 15:16:19
3250
发布2019-06-02 15:16:19
举报
文章被收录于专栏:Bingo的深度学习杂货店
题目描述:

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:
代码语言:javascript
复制
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:
代码语言:javascript
复制
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 实现:
代码语言:javascript
复制
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 条评论
热度
最新
推荐阅读
目录
  • 题目描述:
    • Example 1:
      • Note:
      • 解题思路:
      • Python3 实现:
      领券
      问题归档专栏文章快讯文章归档关键词归档开发者手册归档开发者手册 Section 归档