[数据结构与算法]最小路径和（最基础的动态规划问题）

• 状态定义
  dp[i][j] 表示走到i,j这个点的最小路径。

• 转移方程的确定

  1. 当前节点如果左侧和上侧都不是0的话，那么当前节点最小路径可以是左边的节点的最小路径+当前节点的值 或者是 上边的最小路径的 + 当前节点的值。即 min（dp[i-1][j] + grid[i][j],dp[i][j-1] + grid[i][j]）；
  2. 如果左面为0，那么就只能从上边过来，也就是 dp[i][j-1] + grid[i][j]
  3. 如果上面为0，那么久只能从左边过来，也就是 dp[i-1][j] + grid[i][j]
  4. 如果上面左面都是0，就是起始状态，当前节点。

也可以直接用他给的数组，不影响。

class Solution {
    public int minPathSum(int[][] grid) {
        int width =  grid[0].length;
        int height = grid.length;
        int[][] dp = new int[height][width];
        for(int i = 0 ;i < height;i++){
            for(int j = 0;j < width;j++){
                if(i==0&&j==0) dp[i][j] = grid[i][j];
                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] + grid[i][j],dp[i][j-1] + grid[i][j]);
            }
        }
        return dp[height-1][width-1];
    }
}