【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];
    }
}