LeetCode 64. 最小路径和
题目描述
给定一个包含非负整数的 m x n 网格 grid ,请找出一条从左上角到右下角的路径,使得路径上的数字总和为最小。
说明:每次只能向下或者向右移动一步。
思路
思路:这种题太典了,典型一眼看破的动态规划,当前最小路径和由min(上面一格最小路径和,左边一格最小路径和)+grid[i][j]
组成。需要做的就是:
- 判断当前这一格的上侧和左侧是否都存在,若存在则
dp[i][j]=grid[i][j]+Math.min(dp[i-1][j], dp[i][j-1])
- 若只有上侧存在则
dp[i][j]=dp[i-1][j]+grid[i][j]
- 若只有左侧存在则
dp[i][j]=dp[i][j-1]+grid[i][j]
- 若都不存在(也就是左上角的情况)
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];}
}