[数据结构与算法]力扣之最短路径和问题

题目：

给定一个包含非负整数的?m?x?n?网格?grid?，请找出一条从左上角到右下角的路径，使得路径上的数字总和为最小。

说明：每次只能向下或者向右移动一步。

?

?

思路：

动态规划

?状态定义：????????

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

?转移方程：

????????走到当前单元格 (i,j)的最小路径和 = “从左方单元格 (i-1,j) 与 从上方单元格(i,j?1) 走来的 两个最小路径和中较小的 ” + 当前单元格值 grid[i][j] 。具体分为以下 4?种情况：

? ? ? ? 1、当左边和上边都不是矩阵边界时： 即当i != 0, j != 0时，dp[i][j] = min(dp[i - 1][j], dp[i][j - 1]) + grid[i][j] ；

? ? ? ? 2、当只有左边是矩阵边界时： 只能从上面来，即当i = 0, j != 0时， dp[i][j] = dp[i][j - 1] + grid[i][j] ；

? ? ? ? 3、当只有上边是矩阵边界时： 只能从左面来，即当i!= 0, j = 0时， dp[i][j] = dp[i - 1][j] + grid[i][j] ；

? ? ? ? 4、当左边和上边都是矩阵边界时： 即当i = 0, j = 0时，其实就是起点， dp[i][j] = grid[i][j]；

代码：?

class Solution {
    public int minPathSum(int[][] grid) {
        int adc = grid[0].length;
        int ad = grid.length;
        if(ad==0||adc==0){
            return 0;
        }

        int[][] ap = new int[ad][adc];
        ap[0][0] = grid[0][0];

        for(int i =1;i<ad;i++){
            ap[i][0] = ap[i-1][0] + grid[i][0];
        }

        for(int j=1;j<adc;j++){
            ap[0][j] = ap[0][j-1] + grid[0][j];
        }

        for(int i=1;i<ad;i++){
            for(int j=1;j<adc;j++){
                ap[i][j] = Math.min(ap[i-1][j],ap[i][j-1] )+ grid[i][j];
            }
        }

        return ap[ad-1][adc-1];

    }
}