问题描述

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

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

示例:

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

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/minimum-path-sum
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

解题思路

关于动态规划，请参考：https://github.com/tim-chow/DataStructure/tree/master/%E5%8A%A8%E6%80%81%E8%A7%84%E5%88%92。

本题中的状态转移方程是

• 如果 i == m - 1 and j == n - 1，那么说明已经到达终点，d(i, j) = grid[i][j]
• 如果 i == m - 1，那么说明只能向右移动，d(i, j) = grid[i][j] + d(i, j+1)
• 如果 j == n - 1，那么说明只能向下移动，d(i, j) = grid[i][j] + d(i+1, j)
• 否则，说明既可以向下移动，可以向右移动，d(i, j) = grid[i][j] + min(d(i+1, j), d(i, j+1))

Python 实现

class Solution(object):
    def minPathSum(self, grid):
        """
        :type grid: List[List[int]]
        :rtype: int
        """
        return self._min_path_sum(0, 0, grid, len(grid), len(grid[0]), {})

    def _min_path_sum(self, start_i, start_j, grid, m, n, d):
        if (start_i, start_j) in d:
            return d[(start_i, start_j)]

        if start_i == m - 1 and start_j == n - 1:
            d[(start_i, start_j)] = grid[start_i][start_j]
        elif start_i == m - 1:
            ret = grid[start_i][start_j] + \
                  self._min_path_sum(start_i, start_j+1, grid, m, n, d)
            d[(start_i, start_j)] = ret
        elif start_j == n - 1:
            ret = grid[start_i][start_j] + \
                  self._min_path_sum(start_i+1, start_j, grid, m, n, d)
            d[(start_i, start_j)] = ret
        else:
            ret = grid[start_i][start_j] + min(
                self._min_path_sum(start_i+1, start_j, grid, m, n, d),
                self._min_path_sum(start_i, start_j+1, grid, m, n, d))
            d[(start_i, start_j)] = ret
        return d[(start_i, start_j)]