【LeetCode】64. Minimum Path Sum
2024-08-29 05:45:12
Minimum Path Sum
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的矩阵path,path[i][j]存放从首元素(grid[0][0])到当前元素(grid[i][j])的最短路径长度。
对于每个元素来说,路径是从上或者从左边来的。
也就是说path[i][j] = min(path[i-1][j]+path[i][j-1]) + grid[i][j]。
注意:初始化第一行第一列。
class Solution {
public:
int minPathSum(vector<vector<int> > &grid) {
if(grid.empty() || grid[].empty())
return ;
int m = grid.size();
int n = grid[].size();
vector<vector<int> > path(m, vector<int>(n, ));
path[][] = grid[][];
for(int i = ; i < m; i ++)
path[i][] = path[i-][] + grid[i][];
for(int i = ; i < n; i ++)
path[][i] = path[][i-] + grid[][i];
for(int i = ; i < m; i ++)
{
for(int j = ; j < n; j ++)
{
path[i][j] = min(path[i-][j], path[i][j-]) + grid[i][j];
}
}
return path[m-][n-];
}
};
最新文章
- iOS开发之窥探UICollectionViewController(五) --一款炫酷的图片浏览组件
- SQLServer中的页如何影响数据库性能 (转)
- struts2学习笔记之五:表单数据收集的几种方式
- API 开发实践
- Java线程中run和start方法的区别
- 不错的linux下通用的java程序启动脚本
- 背包问题(Knapsack problem)采用动态规划求解
- Python学习教程(learning Python)--3.3 分支语句的条件表达式详解
- linux 上不去网
- 查看ubuntu的内核版本&;获取roo…
- 06 Django REST Framework 版本控制
- Angular路由——辅助路由
- c语言之字符输入输出和输入验证
- MySQL(介绍,安装,密码操作,权限表)
- [py]python之信用卡ATM
- QQ在开发中的应用
- 创龙OMAPL138的NMI中断
- Zipline Beginner Tutorial
- visio2013密钥
- python再议装饰器