力扣——最小路径和

题目链接：

添加链接描述

题目描述：

思路：

设走到$(i,j)$的最小路径和为$dp(i,j)$，
则： d p ( i , j ) = m i n { d p ( i − 1 , j ) , d p ( i , j − 1 ) } + d p ( i , j ) ; / / 找最小的加起来 dp(i,j) = min\{dp(i-1,j),dp(i,j-1)\}+dp(i,j);//找最小的加起来 dp(i,j)=min{dp(i−1,j),dp(i,j−1)}+dp(i,j);//找最小的加起来
在边界上有:
第一行(i=0)：$$dp(i,j)=dp(i,j-1)+dp(i,j);$$
第一列(j=0):$$dp(i,j)=dp(i-1,j)+dp(i,j);$$

出发点的dp就是本身

实现代码：

class Solution {
    public int minPathSum(int[][] grid) {
        for(int i = 0; i < grid.length; i++){
            for(int j = 0; j < grid[0].length; j++){
                if(i ==0 && j==0) continue;
                else if(i ==0) grid[i][j] = grid[i][j-1] + grid[i][j];
                else if(j==0) grid[i][j] = grid[i-1][j] + grid[i][j];
                else grid[i][j] = Math.min(grid[i-1][j],grid[i][j-1]) + grid[i][j];
            }
        }
        return grid[grid.length-1][grid[0].length-1];
    }
}