day-32 最小路径和

思路
典型的DP问题，状态方程为distance[i][j]=distance[i][j]+Math.min(distance[i][j-1],distance[i-1][j]),边界情况需要单独讨论

解题方法
对二维数组进行遍历，对于当前元素：
1:i0\&\&j0,则distance[i][j]=grid[i][j]
2:i0\&\&j!=0,则distance[i][j]=grid[i][j]+grid[i][j-1]
3:i!=0\&\&j0,则distance[i][j]=grid[i][j]+grid[i-1][j]
4:以上情况皆不满足,则distance[i][j]=grid[i][j]+Math.min(grid[i][j-1],grid[i-1][j])
最后返回distance[m][n]即可

Code

class Solution {

    public int minPathSum(int[][] grid) {

        int m=grid.length;
        int n=grid[0].length;
        for(int i=0;i<m;i++){

            for(int j=0;j<n;j++){

                if(i==0&&j==0){
   }
                else if(i==0&&j!=0){

                    grid[i][j]+=grid[i][j-1];
                }else if(i!=0&&j==0){

                    grid[i][j]+=grid[i-1][j];
                }else{

                    grid[i][j]+=Math.min(grid[i][j-1],grid[i-1][j]);
                }
            }
        }
        return grid[m-1][n-1];
    }
}

原文链接: https://blog.csdn.net/qq_53568730/article/details/138648802

目录