【LeetCode】【算法】64. 最小路径和

LeetCode 64. 最小路径和

题目描述

给定一个包含非负整数的 m x n 网格 grid ，请找出一条从左上角到右下角的路径，使得路径上的数字总和为最小。
说明：每次只能向下或者向右移动一步。

思路

思路：这种题太典了，典型一眼看破的动态规划，当前最小路径和由min(上面一格最小路径和,左边一格最小路径和)+grid[i][j]组成。需要做的就是：

1. 判断当前这一格的上侧和左侧是否都存在，若存在则dp[i][j]=grid[i][j]+Math.min(dp[i-1][j], dp[i][j-1])
2. 若只有上侧存在则dp[i][j]=dp[i-1][j]+grid[i][j]
3. 若只有左侧存在则dp[i][j]=dp[i][j-1]+grid[i][j]
4. 若都不存在（也就是左上角的情况）dp[i][j]=grid[i][j]

代码

class Solution {
    public int minPathSum(int[][] grid) {
        int[][] dp = new int[grid.length][grid[0].length];

        for (int i = 0; i < grid.length; i++) {
            for (int j = 0; j < grid[0].length; j++) {
                if (i - 1 >= 0 && j - 1 >= 0){
                    dp[i][j] = grid[i][j] + Math.min(dp[i-1][j], dp[i][j-1]);
                } else if (i - 1 >= 0) {
                    dp[i][j] = grid[i][j] + dp[i-1][j];
                } else if (j - 1 >= 0) {
                    dp[i][j] = grid[i][j] + dp[i][j-1];
                } else {
                    dp[i][j] = grid[i][j];
                }
            }
        }
        return dp[grid.length - 1][grid[0].length - 1];
    }
}

原文地址：https://blog.csdn.net/passer__jw767/article/details/143720160

免责声明：本站文章内容转载自网络资源，如本站内容侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！