AlgoPressAppearance
0064-最小路径和
https://leetcode.cn/problems/minimum-path-sum
给定一个包含非负整数的 m x n 网格 grid ，请找出一条从左上角到右下角的路径，使得路径上的数字总和为最小。 说明：每次只能向下或者向右移动一步。
示例 1： 
输入：grid = [[1,3,1],[1,5,1],[4,2,1]]
输出：7
解释：因为路径 1→3→1→1→1 的总和最小。
示例 2：
输入：grid = [[1,2,3],[4,5,6]]
输出：12
提示：
m == grid.length
n == grid[i].length
1 <= m, n <= 200
0 <= grid[i][j] <= 100
基本思路
动态规划，dp 表示到目前格子的最小值，因为只能向下或者向右移动，所以状态转移公式如下
扩展数组可以处理边界：有问题，不能用边界0来判断 min
dp[i,j] = min(dp[i-1,j],dp[i,j-1]) + grid[i][j]
参考代码
csharp
public class Solution {
public int MinPathSum(int[][] grid) {
int m = grid.Length;
int n = grid[0].Length;
int[,] dp = new int[m,n];
for(int i=0;i<m;i++){
for(int j=0;j<n;j++){
if(i==0 && j==0){
dp[0,0] = grid[0][0];
}
else if(i==0){
dp[i,j] = dp[i,j-1] + grid[i][j];
}
else if(j==0){
dp[i,j] = dp[i-1,j] + grid[i][j];
}
else{
dp[i,j] = Math.Min(dp[i-1,j],dp[i,j-1]) + grid[i][j];
}
}
}
return dp[m-1,n-1];
}
}
参考代码2：优化数组
dp[i,j] = min(dp[i-1,j],dp[i,j-1]) + grid[i][j]
dp[i,j] 只用到dp[i-1]的数据，再前面的数据用不到了
i-1 就是上一次的数据，我们用上一次的循环的结果来表示就是 dp[j]
dp[j] = min(dp[j],dp[j-1]) + grid[i][j];
csharp
public class Solution {
public int MinPathSum(int[][] grid) {
int m = grid.Length;
int n = grid[0].Length;
int[] dp = new int[n];
for(int i=0; i<m; i++){
for(int j=0;j<n;j++){
if(i==0 && j==0){
dp[0] = grid[0][0];
}
else if(i==0){
dp[j] = dp[j-1] + grid[i][j];
}
else if(j==0){
dp[j] = dp[j] + grid[i][j];
}
else{
dp[j] = Math.Min(dp[j],dp[j-1])+grid[i][j];
}
}
}
return dp[n-1];
}
}