【一天一道LeetCode】#64. Minimum Path Sum.md
2024-08-26 09:58:00
一天一道LeetCode
本系列文章已全部上传至我的github,地址:ZeeCoder‘s Github
欢迎大家关注我的新浪微博,我的新浪微博
欢迎转载,转载请注明出处
(一)题目
Given a m x n grid filled with non-negative numbers, find a path from top left to bottom right which minimizes the sum of all numbers along its path.
Note: You can only move either down or right at any point in time.
(二)解题
题目大意:求从m*n的矩阵的左上角走到右下角的所有路径中,路径上的值加起来最小的路径。
思路可以参考:【一天一道LeetCode】#62. Unique Paths &&【一天一道LeetCode】#63. Unique Paths II
class Solution {
public:
int minPathSum(vector<vector<int>>& grid) {
int row = grid.size();
int col = grid[0].size();
vector<vector<int>> path = grid; //path纪录当前点到右下角点的路径和最小值
//对矩阵进行改造,可以避免考虑越界
vector<int> temp(col,2147483647);
path.push_back(temp);
for(int i = 0 ; i < row ; i++)
{
path[i].push_back(2147483647);
}
for(int i = row-1 ; i >=0 ; i--)
for(int j = col-1 ; j>=0;j--)
{
if (i==row-1&&j==col-1) continue;//终点直接跳过
if(path[i][j] ==grid[i][j])
{
path[i][j] +=min(path[i+1][j],path[i][j+1]);//每一点到终点的路径和最小值等一向下和向右走的最小值加上自身
}
}
return path[0][0];
}
};
最新文章
- .net字符串数组查找方式效率比较
- HDU 3461 Code Lock(并查集)
- src url href uri的区别和联系
- 微信公众号开发中遇到的几个bug
- CSS 会被继承的属性
- CSS选择器,CSS3选择器
- Spring REST实践之安全
- Decorator设计模式浅谈
- div整体布局分析
- Android多线程.断点续传下载
- 【转】shell脚本实现多台服务器自动巡检--可参考学习
- android新窗口以及传值
- 使用js主函数的原因是等文档加载完了才给里面的元素添加东西 如果不使用主函数则文档加载时候无法找到元素则不能成功给元素添加事件
- Linux 练习题(2)
- rac添加新节点的步骤与方法2
- Codeforces Beta Round #63 (Div. 2)
- day17(tomcat的安装,HTTP)
- switch语句语法
- USB Mass Storage Class – Bulk Only Transport - Error Handling
- SYSCALL_DEFINE3