最小路径和

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

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

 

示例 1：


输入：grid = [[1,3,1],[1,5,1],[4,2,1]]
输出：7
解释：因为路径 1→3→1→1→1 的总和最小。
示例 2：

输入：grid = [[1,2,3],[4,5,6]]
输出：12
 

提示：

m == grid.length
n == grid[i].length
1 <= m, n <= 200
0 <= grid[i][j] <= 100
通过次数160,664提交次数237,325

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/minimum-path-sum
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

最简单的动态规划

因为位置（i，j）只能由（i-1,j）或者（i,j-1）走到,因此dp[i][j]=Math.min(dp[i - 1][j], dp[i][j - 1])+ grid，此外需要考虑边际条件，i-1<0以及j-1<0

class Solution {
    public int minPathSum(int[][] grid) {
        int h = grid.length;
        int w = grid[0].length;
        int[][] dp = new int[h][w];
        dp[0][0] = grid[0][0];
        for (int i = 0; i < h; i++) {
            for (int j = 0; j < w; j++) {
                if (i - 1 >= 0 && j - 1 >= 0) {
                    dp[i][j] = Math.min(dp[i - 1][j], dp[i][j - 1]) + grid[i][j];
                } else if (i - 1 >= 0) {
                    dp[i][j] = dp[i - 1][j] + grid[i][j];
                } else if (j - 1 >= 0) {
                    dp[i][j] = dp[i][j - 1] + grid[i][j];
                }

            }
        }
        return dp[h - 1][w - 1];
    }
}

赏

谢谢你请我吃糖果

微信