64. 最小路径和

给定一个包含非负整数的 m x n 网格 grid ，请找出一条从左上角到右下角的路径，使得路径上的数字总和为最小。 说明：每次只能向下或者向右移动一步。

代码语言：javascript复制

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];

    }
}

grid

0 人点赞