// @Title: 最小路径和 (Minimum Path Sum)
// @Author: qisiii
// @Date: 2024-10-13 16:25:14
// @Runtime: 4 ms
// @Memory: 46.5 MB
// @comment: 动态规划
// @flag: GREEN
class Solution {
    int min=Integer.MAX_VALUE;
    public int minPathSum(int[][] grid) {
        //dp数组应该表示走到当前点的时候路径最小和
        int[][] dp=new int[grid.length][grid[0].length];
        for(int i=0;i<grid.length;i++){
            for(int j=0;j<grid[0].length;j++){
                if(i==0&&j==0){
                    dp[i][j]=grid[i][j];
                }else if(i==0){
                    dp[i][j]=dp[i][j-1]+grid[i][j];
                }else if(j==0){
                    dp[i][j]=dp[i-1][j]+grid[i][j];
                }else{
                    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];
    }
}