最小路径和

题目

给定一个包含非负整数的 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数组)；

  • 状态转移方程：

    

• 代码：

  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")