题目
Given a m x n grid filled with non-negative numbers, find a path from top left to bottom right which minimizes the sum of all numbers along its path.
Note: You can only move either down or right at any point in time.

例子
Input:
[
  [1,3,1],
  [1,5,1],
  [4,2,1]
]
Output: 7
Explanation: Because the path 1→3→1→1→1 minimizes the sum.
1
2
3
4
5
6
7
8
问题解析
给定一个m*n的数组，数组中包含非负数，从该数组左上角到该数组右下角的最小路径和。（只能向下或者向右移动）
链接：LeetCode：https://leetcode.com/problems/minimum-path-sum/description/

解题思路
典型的动态规划题。动态规划三要素：问题的阶段，每个阶段的状态以及从前一个阶段转化到后一个阶段之间的递推关系。递推关系必须是从次小的问题开始到较大问题之间的转化，从这个角度来说，动态规划往往可以用递归程序来实现，不过因为递推可以充分利用前面保存的子问题的解来减少重复计算，所以对于大规模问题来说，有递归不可比拟的优势，这也是动态规划算法的核心之处。确定了动态规划的这三要素，整个求解过程就可以用一个最优决策表来描述，最优决策表是一个二维表，其中行表示决策的阶段，列表示问题状态，表格需要填写的数据一般对应此问题在某个阶段某个状态下的最优值（如最短路径，最长公共子序列，最大价值等），填表的过程就是根据递推关系，从1行1列开始，以行或者列优先的顺序，依次填写表格，最后根据整个表格的数据通过简单的取舍或者运算求得问题的最优解。

首先找出递推关系，比如设存放起点到每个格子 i，j 的最小路径和的二维数组为 MPS[j]，递推公式为：

MPS[j] = Min（MPS[i-1][j]，MPS[j-1]）+ grid[j]；
1
格子 i，j 的MPS值可能有两个来源：其左侧格子 i，j-1 或者其上侧格子 i-1，j ；取这两个来源的较小MPS值，再加上当前格子的值 grid[j] 即为结果。！！！！

由于是从左上方向右下方走，故我们可以利用一个双重循环来进行迭代计算，外层循环以行为单位，内层循环以列为单位，这样可以利用已经计算好的阶段 、状态来计算当前格子的结果，因为每次计算某个格子时，其左侧格子和上侧格子结果已经算好，这也是动态规划比递归要快的原因。
代码（python）：

class Solution(object):
    def minPathSum(self, grid):
        """
        :type grid: List[List[int]]
        :rtype: int
        """
        m = len(grid)
        n = len(grid[0])
        for i in range(m):
            for j in range(n):
                if i==0 and j==0:
                    continue
                if i==0 and j!=0:
                    grid[j]=grid[j-1]+grid[j]
                    continue
                if i!=0 and j==0:
                    grid[j]=grid[i-1][j]+grid[j]
                    continue
                if i!=0 and j!=0:
                    grid[j]=min(grid[i-1][j],grid[j-1])+grid[j]
                    continue
        return grid[m-1][n-1]

input = [[1,3,1],
      [1,5,1],
      [4,2,1]]

solution = Solution()
output = solution.minPathSum(li)
print(output)
---------------------
作者：Never-Giveup
来源：CSDN
原文：https://blog.csdn.net/qq_36653505/article/details/81081481
版权声明：本文为博主原创文章，转载请附上博文链接！

奈斯