110.Minimum Path Sum

1.Description(Easy)

Given a m x n grid filled with non-negative numbers, find a path from top left to bottom right which minimizes the sum of all numbers along its path.

Notice

You can only move either down or right at any point in time.

2.Code

坐标型动态规划

• state: f[x][y]从起点走到x,y的最短路径

• function: f[x][y] = min(f[x-1][y], f[x][y-1]) + A[x][y]

• intialize: f[i][0] = sum(0,0 ~ i,0)

• f[0][i] = sum(0,0 ~ 0,i)

• answer: f[n-1][m-1]

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


        if(grid==null || grid.length==0){
            return -1;
        }
        if(grid[0]==null || grid[0].length==0){
            return -1;
        }


        int n=grid.length;
        int m=grid[0].length;
        //state:min path sum from(0.0) to (x,y)
        int[][] minpath=new int[n][m];

        //initialization:
        minpath[0][0]=grid[0][0];
        for(int i=1;i<n;i++){
            minpath[i][0]=minpath[i-1][0]+grid[i][0];
        }
        for(int i=1;i<m;i++){
            minpath[0][i]=minpath[0][i-1]+grid[0][i];
        }

        //function://to down or to right
        for(int i=1;i<n;i++){
            for(int j=1;j<m;j++){
                minpath[i][j]=Math.min(minpath[i-1][j], minpath[i][j-1])+grid[i][j];
            }
        }

        //answer:
        return minpath[n-1][m-1];

    }