64. 最小路径和

class Solution {
    public int minPathSum(int[][] grid) {
        /**
        动态规划  
        第一行的最小路径和只能有向右而来 所以累加  
        第一列也是如此
         */
         int [][] dp=new int[grid.length][grid[0].length];
         dp[0][0]=grid[0][0];//到当前方块(包含当前方块)的最小路径和
         for(int i=1;i<grid.length;i++){
             dp[i][0]+=(dp[i-1][0]+grid[i][0]);
         }

         for(int j=1;j<grid[0].length;j++){
             dp[0][j]+=(dp[0][j-1]+grid[0][j]);
         }

         for(int i=1;i<grid.length;i++){
             for(int j=1;j<grid[0].length;j++){
                 dp[i][j]=Math.min(dp[i-1][j],dp[i][j-1])+grid[i][j];
             }
         }
        
         return  dp[grid.length-1][grid[0].length-1];

    }
}