思路 二维动态规划

public int minPathSum(int[][] grid) {
        int r = grid.length;
        int c = grid[0].length;
        int[][] dp = new int[r][c];
        //从最后一行开始计算
        for(int i=r-1;i>=0;i--){
            //从最后一列向前计算
            for(int j=c-1;j>=0;j--){
                if(i==r-1&&j==c-1)     //如果是右下角的元素 则直接赋值
                    dp[i][j]=grid[i][j];
                else if(i==r-1)        //如果是最后一行
                    dp[i][j]=grid[i][j]+dp[i][j+1];
                else if(j==c-1)        //如果是最后一列
                    dp[i][j]=grid[i][j]+dp[i+1][j];
                //如果是普通的情况
                else dp[i][j] = grid[i][j]+Math.min(dp[i][j+1],dp[i+1][j]);
            }
        }
        return dp[0][0];
    }