[数据结构与算法]动态规划解决最小路径和

?题解：遍历改二维数组每个位置，记录到当前位置最短路径和

定义

?设?dpdp?为大小?m \times nm×n?矩阵，其中?dp[i][j]dp[i][j]?的值代表直到走到?(i,j)(i,j)?的最小路径和。

转移方程：?

1当左边和上边都不是矩阵边界时：

grid[i][j]=grid[i][j]+Math.min(grid[i-1][j],grid[i][j-1]);

2.当只有左边是矩阵边界时：

grid[i][j]=grid[i][j]+grid[i][j-1];

3.当只有上边是矩阵边界时：

grid[i][j]=grid[i][j]+grid[i-1][j];

4.当左边和上边都是矩阵边界时：

?//就算是起点
? ? ? ? ? ? ? ? if(i==0&&j==0) continue;

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]+grid[i][j-1];
                    //挨着上边境
                }else if(j==0){
                    grid[i][j]=grid[i][j]+grid[i-1][j];
                }else
                //都没挨着
                grid[i][j]=grid[i][j]+Math.min(grid[i-1][j],grid[i][j-1]);
            }

        }
//返回右下角最短路径
       return grid[grid.length - 1][grid[0].length - 1];
    }
}

?