LeetCode -- Minimum Path Sum
题目描述：
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.
在一个m*n的矩阵中，从左上角的位置开始向右下移动，每次只能走右或下。每个单元格包含1个非负数得到和s，每走一步累加这个数字。求从左上到右下路径中的最小s。
思路：
1.dp问题。初始化dp[0,0] = grid[0,0]。
2.初始化第一行和第一列：dp[i,0] = dp[i-1,0] + grid[i,0]；dp[0,i] = dp[0,i-1] + grid[0,i]
3.从[i,j]（初始化为[1,1]）的位置向下走，从dp[i-1,j]与dp[i,j-1]中取最小值min，设置dp[i,j] = min + grid[i,j]。
4.最后的dp[row-1,col-1]即为最小和。
实现代码：
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.
在一个m*n的矩阵中，从左上角的位置开始向右下移动，每次只能走右或下。每个单元格包含1个非负数得到和s，每走一步累加这个数字。求从左上到右下路径中的最小s。
思路：
1.dp问题。初始化dp[0,0] = grid[0,0]。
2.初始化第一行和第一列：dp[i,0] = dp[i-1,0] + grid[i,0]；dp[0,i] = dp[0,i-1] + grid[0,i]
3.从[i,j]（初始化为[1,1]）的位置向下走，从dp[i-1,j]与dp[i,j-1]中取最小值min，设置dp[i,j] = min + grid[i,j]。
4.最后的dp[row-1,col-1]即为最小和。
实现代码：
public class Solution {
public int MinPathSum(int[,] grid) {
var row = grid.GetLength(0);
var col = grid.GetLength(1);
var dp = new int[row,col];
dp[0,0] = grid[0,0];
// set first column
for(var i = 1;i < row; i ++){
dp[i,0] = dp[i-1,0] + grid[i,0];
}
// set first row
for(var i = 1;i < col; i ++){
dp[0,i] = dp[0,i-1] + grid[0,i];
}
// from [1,1] to [m,n]
for(var i = 1;i < row; i++){
for(var j = 1;j < col; j++){
dp[i,j] = Math.Min(dp[i-1,j], dp[i,j-1]) + grid[i,j];
}
}
return dp[row-1,col-1];
}
}