用c++实现给定一个包含非负整数的mxn网格grid，请找出一条从左上角到右下角的路径，使得路径上的数字总和为最小

题目描述

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

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

示例

输入:

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

输出: 7

解释: 因为路径1→3→1→1→1的总和最小。

算法

(动态规划) $O(n^2)$

可以使用动态规划来解决这个问题。

设dp(i,j)为从左上角出发到(i,j)的路径上所有数字的最小和，则易得到递推式：

$$dp(i,j)=\min(dp(i-1,j),dp(i,j-1))+grid(i,j)$$

边界条件为：

$$dp(i,0)=dp(0,j)=\sum_{k=0}^j grid(0,k),\sum_{k=0}^i grid(k,0)$$

最终答案为dp(m-1,n-1)。

时间复杂度分析：一共有$nm$个状态，每个状态需要$O(1)$的时间来转移，故总时间复杂度为$O(nm)$。

C++ 代码

class Solution {
public:
int minPathSum(vector<vector<int>>& grid) {
int m=grid.size(),n=grid[0].size();
vector<vector<int>> dp(m,vector<int>(n,0));
dp[0][0]=grid[0][0];
for(int i=1;i<m;i++) dp[i][0]=dp[i-1][0]+grid[i][0];
for(int i=1;i<n;i++) dp[0][i]=dp[0][i-1]+grid[0][i];
for(int i=1;i<m;i++)
for(int j=1;j<n;j++)
dp[i][j]=min(dp[i-1][j],dp[i][j-1])+grid[i][j];
return dp[m-1][n-1];
}
};