[LeetCode]64. 最小路径和
LeetCode 路径 最小 64
2023-09-11 14:18:49 时间
算法标签 DP
题目简叙
思路
典型DP
数值累加
状态转移方程如下:
当前位置所处的 行与列 处于为边界时候:
当前的值即为 自身本身
当前位置所处的 行 处于为边界时候:
当前的值即为 上方 的累加
当前位置所处的 列 处于为边界时候:
当前的值即为 左方 的累加
当都不属于的时候
当前的值即为 上方和左方最小值 的累加
代码
class Solution {
public:
int minPathSum(vector<vector<int>>& grid) {
for(int i=0;i<grid.size();i++)
for(int j=0;j<grid[0].size();j++)
if(i==0&&j==0)continue;
else if(i==0)grid[i][j]+=grid[i][j-1];
else if(j==0)grid[i][j]+=grid[i-1][j];
else grid[i][j]+=min(grid[i-1][j],grid[i][j-1]);
return grid[grid.size()-1][grid[0].size()-1];
}
};
AC记录
相关文章
- Java实现 LeetCode 1111 有效括号的嵌套深度(阅读理解题,位运算)
- Java实现 LeetCode 479 最大回文数乘积
- Java实现 LeetCode 335 路径交叉
- Java实现 LeetCode 198 打家劫舍
- Java实现 LeetCode 113 路径总和 II
- Java实现 LeetCode 64 最小路径和
- Java实现 LeetCode 62 不同路径
- leetcode 167. 两数之和 II - 输入有序数组----双指针篇六,二分篇二
- leetcode 1289. 下降路径最小和 II
- leetcode 120. 三角形最小路径和
- 【LeetCode Python实现】329. 矩阵中的最长递增路径(困难)
- [LeetCode] 437. 路径总和 III ☆☆☆(递归)
- [LeetCode] 64. 最小路径和 ☆☆☆(动态规划)
- 【LeetCode】Repeated DNA Sequences 解题报告
- 【LeetCode】64. 最小路径和
- 【Leetcode】151. 颠倒字符串中的单词
- 【LeetCode】120.三角形最小路径和
- 【LeetCode】113. 路径总和 II