题目链接
思路
分析动态规划题目的时候只需要考虑最后一个阶段,因为所有的阶段转化都是相同的,考虑最后一个阶段容易发现规律
表示状态
假设到了右下角,考虑一下我们要存储的信息
- 走到最后坐标的最小步数
- 当前坐标的信息,用来判断是否走到了右下角
很容易联想到使用二维数组 dp[i][j]
来表示在坐标 \((i,j)\) 处的最小步数。
找状态转移方程
因为只能往下或者往右走并且
\[dp[i][j] = min(dp[i - 1][j], dp[i][j - 1]) + grid[i][j] \]边界处理
我们只需要处理第一行和第一列就行。
第一行处理为
dp[0][i] = i == 0 ? grid[0][i] : grid[0][i] + dp[0][i - 1];
第一列处理为
dp[i][0] = i == 0 ? grid[i][0] : grid[i][0] + dp[i - 1][0];
代码
class Solution {
public int minPathSum(int[][] grid) {
// dp[i][j] = min(dp[i - 1][j], dp[i][j - 1]) + grid[i][j]
int[][] dp = new int[grid.length][grid[0].length];
for(int i = 0; i < dp[0].length; i++){
dp[0][i] = i == 0 ? grid[0][i] : grid[0][i] + dp[0][i - 1];
}
for(int i = 0; i < dp.length; i++){
dp[i][0] = i == 0 ? grid[i][0] : grid[i][0] + dp[i - 1][0];
}
for(int i = 1; i < grid.length; i++){
for(int j = 1; j < grid[i].length; j++){
dp[i][j] = Math.min(dp[i - 1][j], dp[i][j - 1]) + grid[i][j];
}
}
return dp[grid.length - 1][grid[0].length - 1];
}
}
标签:int,++,length,grid,DP,64,LeetCode,dp
From: https://www.cnblogs.com/shixuanliu/p/17280369.html