题目
m == grid.length n == grid[i].length 1 <= m, n <= 200 0 <= gridi <= 100
思路
此题数据达到200 * 200搜索会超时。
因为每次移动只能向下或向右，所以要到达某个方块只能由其上边的方块或左边的方块到达（左上角方块除外）。
定义dp[i][j]：到达i,j位置所需要的最少步数。 状态转移方程：由于方块只能向下或向右移动，那么dp[i][j]的值就只和dp[i - 1][j]和dp[i][j - 1]有关，由于找最短路径所以在dp[i - 1][j]和dp[i][j - 1]取最小然后加上grid[i][j]表示到达dp[i][j]所需要的最短路径。 dp[0][0] = grid[0][0]
确定好转移方程后两层遍历可以把dp数组填充，然后取右下角就是所求答案。
代码语言：javascript复制class Solution {
public:
int minPathSum(vector<vector<int>>& grid) {
int n = grid.size(), m = grid[0].size();
int dp[n][m];
dp[0][0] = grid[0][0];
for (int i = 0; i < n; i ) {
for (int j = 0; j < m; j ) {
if (j - 1 >= 0 && i - 1 >= 0)
dp[i][j] = min(dp[i][j - 1], dp[i - 1][j]) grid[i][j];
else if (j - 1 >= 0)
dp[i][j] = dp[i][j - 1] grid[i][j];
else if (i - 1 >= 0)
dp[i][j] = dp[i - 1][j] grid[i][j];
}
}
return dp[n - 1][m - 1];
}
};
