动态规划-64. 最小路径和
点击蓝字关注我，一起成长
题目
给定一个包含非负整数的 m x n 网格，请找出一条从左上角到右下角的路径，使得路径上的数字总和为最小。
说明：每次只能向下或者向右移动一步。
2
样例
示例1：
[
[1,3,1],
[1,5,1],
[4,2,1]
]
输出: 7
解释: 因为路径 1→3→1→1→1 的总和最小。
3
样例解读
由题目可以确定：
本题可以看出，假设我们要到达[i , j] ,有两种途径：一种是通过 [i - 1, j] ；一种是通过 [i, j - 1] 。
4
解答与代码
由上分析可以得到：
（1）创建dp数组，dp[i][j] 表示从 左上角即[0 ,0]到 [i , j] 的路径和。
（2）由上面解读，我们可以得到状态转移方程为：
dp[i , j] = Math.min(dp[i - 1][j] , dp[i][j - 1]) + grid[i][j];
答案：
class Solution {public int minPathSum(int[][] grid) {//dp[i][j] = min(dp[i - 1][j], dp[i][j - 1]) + grid[i][j];int n = grid.length;int m = grid[0].length;int[][] dp = new int[n][m];for(int i = 0; i < n; i++){for(int j = 0;j<m;j++){if(i == 0){if(j == 0)dp[i][j] = grid[i][j];else{dp[i][j] = dp[i][j - 1] + grid[i][j];}}else if(j == 0){dp[i][j] = dp[i - 1][j] + grid[i][j];}else{dp[i][j] = Math.min(dp[i - 1][j], dp[i][j - 1]) + grid[i][j];}}}return dp[n - 1][m - 1];}}
5
预告
本次专题：动态规划算法
明天预告题目：
Leetcode - 91. 解码方法
● 扫码关注我
题目素材来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/unique-paths-ii
喜欢我们的内容就点“在看”分享给小伙伴哦