题解 | #求路径# 简单易理解的动态规划算法

动态规划算法分析：  1.问题：求(0,0)到(m-1,n-1)的最小路径之和,更新数组grid(i,j)表示为到达这个位置的最短路径之和  2.状态定义：转化为子问题就是求(0,0)到(i,j)的最短路径之和，但是要首先计算第一行和第一列的这些位置的最短路径之和，注意处理越界的问题  3.状态转移方程：当i==0时，grid(0,j)=grid(0,j-1)+grid(0,j),当j==0时，grid(i,0)=grid(i-1,0)+grid(i,0)，其他情况就是先求出上一行对应的元素跟前一列对应的元素的最小值，然后再加上这个元素本身  4.状态初始化：这里把第一行第一个元素当做初始值，也就是grid(0,0)就是到达这个元素的最短路径  5.返回结果：求得grid(m-1,n-1)的值

public class SumOfMinimumPaths {
    public static int minPathSum(int[][] grid) {
        if(grid.length==0){
            return 0;
        }
        int row=grid.length;
        int col=grid[0].length;
        int i=0;
        int j=0;
        //处理第一列的情况
        for(i=1;i<row;i++){         //这里i不能从0开始，会造成越界，所以应该从0开始，j就是0，不能写成j，不然也会越界
            grid[i][0]=grid[i-1][0]+grid[i][0];
        }
        //处理第一行的情况
        for(j=1;j<col;j++){         //这里j也不能从0开始，会造成越界，所以应该从0开始，i就是0，不能写成i，不然也会越界
            grid[0][j]=grid[0][j-1]+grid[0][j];
        }
        //其他情况
        for( i=1;i<row;i++){
            for( j=1;j<col;j++){
                grid[i][j]=Math.min(grid[i-1][j],grid[i][j-1])+grid[i][j];//先算出上一行和前一列的最小值，然后加上这个元素就是到达这个位置的最短路径之和
            }
        }
        return grid[row-1][col-1];//返回最后一个元素的最短路径之和
    }
}