64.最小路和

原创
2020/07/23 10:08
阅读数 22

64.最小路和

链接

给定一个包含非负整数的 m x n 网格,请找出一条从左上角到右下角的路径,使得路径上的数字总和为最小。 说明:每次只能向下或者向右移动一步。

示例:
输入:
[
  [1,3,1],
  [1,5,1],
  [4,2,1]
]
输出: 7
解释: 因为路径 1→3→1→1→1 的总和最小。

dp代码实现

  • 遍历方向为:向右,向下
  • 状态转移方程: dp[i][j] = min(dp[i][j-1], dp[i-1][j]) + grid[i][j]
  • 初始状态: 第一行,第一列
from typing import List


class Solution:
    def minPathSum(self, grid: List[List[int]]) -> int:
        r = len(grid)
        c = len(grid[0])
        dp = [[0]*c for _ in range(r)]
        dp[0][0] = grid[0][0]
        # 第一行
        for j in range(1, c):
            dp[0][j] = dp[0][j-1] + grid[0][j]

        # 第一列
        for j in range(1, r):
            dp[j][0] = dp[j-1][0] + grid[j][0]

        for i in range(1, r):
            for j in range(1, c):
                dp[i][j] = min(dp[i-1][j], dp[i][j-1]) + grid[i][j]

        return dp[-1][-1]


def main():
    grid = [
        [1, 3, 1],
        [1, 5, 1],
        [4, 2, 1]
    ]
    ret = Solution().minPathSum(grid)
    print(ret)


if __name__ == '__main__':
    main()
展开阅读全文
0
0 收藏
分享
加载中
更多评论
打赏
0 评论
0 收藏
0
分享
返回顶部
顶部