leetcode.64. 最小路径和---常规dp
发布日期:2021-06-28 15:44:00
浏览次数:3
分类:技术文章
本文共 503 字,大约阅读时间需要 1 分钟。
64. 最小路径和
给定一个包含非负整数的 m x n 网格 grid ,请找出一条从左上角到右下角的路径,使得路径上的数字总和为最小。
说明:每次只能向下或者向右移动一步。
示例 1:输入:grid = [[1,3,1],[1,5,1],[4,2,1]]输出:7解释:因为路径 1→3→1→1→1 的总和最小。示例 2:输入:grid = [[1,2,3],[4,5,6]]输出:12 提示:m == grid.lengthn == grid[i].length1 <= m, n <= 2000 <= grid[i][j] <= 100
题解:
常规dp问题,我们发现坐标为(i,j)时其只能要么从(i-1,j)下移得到,要么从(i,j-1)右移得到,因此分两种进行求max即可。当然需要注意一下边界问题。
代码:
int minPathSum(int** grid, int gridSize, int* gridColSize){ int dp[gridSize][gridColSize[0]]; dp[0][0] = grid[0][0]; for(int i=0;i
转载地址:https://blog.csdn.net/xiangguang_fight/article/details/115795982 如侵犯您的版权,请留言回复原文章的地址,我们会给您删除此文章,给您带来不便请您谅解!
发表评论
最新留言
做的很好,不错不错
[***.243.131.199]2024年04月18日 00时47分10秒
关于作者
喝酒易醉,品茶养心,人生如梦,品茶悟道,何以解忧?唯有杜康!
-- 愿君每日到此一游!
推荐文章
linux安装svn并设置自启动
2019-04-29
svn常用命令
2019-04-29
python2网页采集案例
2019-04-29
svn的服务端配置
2019-04-29
python3 urllib和requests模块
2019-04-29
Axure常见的几种原型图
2019-04-29
svn的checkout与export的区别与使用
2019-04-29
js实现点击复制功能
2019-04-29
phpquery采集案例
2019-04-29
jsp内置对象request的常用方法
2019-04-29
javascript 0和-0
2019-04-29
jsDelivr使用小记
2019-04-29
AJAX_ Asynchronous JavaScript and XML
2019-04-29
Vue_基本入门
2019-04-29
Java(1)
2019-04-29
Java(2)
2019-04-29
Java(3)
2019-04-29
react使用antd警告:Warning: findDOMNode is deprecated in StrictMode. findDOMNode was passed an instance
2019-04-29
react 使用router 和 ts 进行页面跳转报错
2019-04-29
更改vue项目的浏览器图标与标头
2019-04-29