美文网首页
Leetcode 64 最小路径和

Leetcode 64 最小路径和

作者: SunnyQjm | 来源:发表于2020-06-27 09:15 被阅读0次

最小路径和

题目

给定一个包含非负整数的 m x n 网格,请找出一条从左上角到右下角的路径,使得路径上的数字总和为最小。

说明:每次只能向下或者向右移动一步。

  • 示例:

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

解答

  • 思路:

    • 采用动态规划;

    • dp[i][j] => 表示第i + 1行第j + 1列的网格到右下角网格的最短路径开销(本题可以直接复用grid作为dp数组);

    • 状态转移方程:

      f(i, j ) = \begin{cases}\mbox{grid}[i][j], & i == m - 1 \&\& j == n - 1 \\ \mbox{grid}[i][j] + f(i + 1, j) & i < m - 1 \&\& j == n - 1 \\ \mbox{grid}[i][j] + f(i, j + 1) & i == m - 1 \&\& j < n - 1 \\ \mbox{grid}[i][j] + min\{f(i + 1, j), f(i, j + 1)\} & i < m - 1 \&\& j < n - 1\end{cases}

  • 代码:

    def minPathSum(self, grid):
        """
        :type grid: List[List[int]]
        :rtype int
    
        (knowledge)
    
        思路:
        1. 采用动态规划;
        2. dp[i][j] => 表示第i + 1行第j + 1列的网格到右下角网格的最短路径开销(本题可以直接复用grid作为dp数组)
        3. 状态转移方程:
            f(i, j) = grid[i][j]                                        i = m-1 && j = n - 1
                      grid[i][j] + f(i + 1, j)                          i < m - 1 && j = n - 1
                      grid[i][j] + f(i, j + 1)                          i = m - 1 && j < n - 1
                      grid[i][j] + min{f(i + 1, j), f(i, j + 1)}        i < m - 1 && j < n - 1
        """
        m, n = len(grid), len(grid[0])
    
        # 先处理最右侧一排
        for i in range(m - 2, -1, -1):
            grid[i][n - 1] += grid[i + 1][n - 1]
    
        # 先处理最底下一行
        for j in range(n - 2, -1, -1):
            grid[m - 1][j] += grid[m - 1][j + 1]
    
        for i in range(m - 2, -1, -1):
            for j in range(n - 2, -1, -1):
                grid[i][j] += min(grid[i + 1][j], grid[i][j + 1])
    
        return grid[0][0]
    

测试验证

class Solution:
    def minPathSum(self, grid):
        """
        :type grid: List[List[int]]
        :rtype int

        (knowledge)

        思路:
        1. 采用动态规划;
        2. dp[i][j] => 表示第i + 1行第j + 1列的网格到右下角网格的最短路径开销(本题可以直接复用grid作为dp数组)
        3. 状态转移方程:
            f(i, j) = grid[i][j]                                        i = m-1 && j = n - 1
                      grid[i][j] + f(i + 1, j)                          i < m - 1 && j = n - 1
                      grid[i][j] + f(i, j + 1)                          i = m - 1 && j < n - 1
                      grid[i][j] + min{f(i + 1, j), f(i, j + 1)}        i < m - 1 && j < n - 1
        """
        m, n = len(grid), len(grid[0])

        # 先处理最右侧一排
        for i in range(m - 2, -1, -1):
            grid[i][n - 1] += grid[i + 1][n - 1]

        # 先处理最底下一行
        for j in range(n - 2, -1, -1):
            grid[m - 1][j] += grid[m - 1][j + 1]

        for i in range(m - 2, -1, -1):
            for j in range(n - 2, -1, -1):
                grid[i][j] += min(grid[i + 1][j], grid[i][j + 1])

        return grid[0][0]


if __name__ == '__main__':
    solution = Solution()
    print(solution.minPathSum([[1, 3, 1], [1, 5, 1], [4, 2, 1]]), "= 7")

相关文章

  • LeetCode 64. 最小路径和 | Python

    64. 最小路径和 题目来源:力扣(LeetCode)https://leetcode-cn.com/proble...

  • 【D13】最小路径和 & 爬楼梯 (LC 64&70)

    64. 最小路径和[https://leetcode-cn.com/problems/minimum-path-s...

  • [LeetCode]64、最小路径和

    题目描述 给定一个包含非负整数的 m x n 网格,请找出一条从左上角到右下角的路径,使得路径上的数字总和为最小。...

  • LeetCode 64 最小路径和

    64. 最小路径和 给定一个包含非负整数的 m x n 网格,请找出一条从左上角到右下角的路径,使得路径上的数字总...

  • Leetcode 64 最小路径和

    最小路径和 题目 给定一个包含非负整数的 m x n 网格,请找出一条从左上角到右下角的路径,使得路径上的数字总和...

  • leetcode 64最小路径和

    很简单的题目 多打了一个等号 结果找错找了半天 也是使用了dp来完成这个题目这应该算是一道用来比较好理解dp的一道题目

  • Leetcode-64:最小路径和

    描述:给定一个包含非负整数的 m x n 网格,请找出一条从左上角到右下角的路径,使得路径上的数字总和为最小。 说...

  • Leetcode64最小路径和

    题目 给定一个包含非负整数的 m x n 网格,请找出一条从左上角到右下角的路径,使得路径上的数字总和为最小。说明...

  • leetcode#64 最小路径和

    题目 给定一个包含非负整数的 m x n 网格,请找出一条从左上角到右下角的路径,使得路径上的数字总和为最小。 说...

  • leetcode_64最小路径和

    直接在原矩阵上改数据,控制第一行和第一列更新为当前值和前面或上面的值累加,其他位置则判断从上面还是左边的值更小并累...

网友评论

      本文标题:Leetcode 64 最小路径和

      本文链接:https://www.haomeiwen.com/subject/dgwufktx.html