leetcode.64. 最小路径和---常规dp
发布日期:2021-06-28 15:44:00
浏览次数:2
分类:技术文章
本文共 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 如侵犯您的版权,请留言回复原文章的地址,我们会给您删除此文章,给您带来不便请您谅解!
发表评论
最新留言
不错!
[***.144.177.141]2024年04月27日 10时49分21秒
关于作者
喝酒易醉,品茶养心,人生如梦,品茶悟道,何以解忧?唯有杜康!
-- 愿君每日到此一游!
推荐文章
微信小程序-在button添加icon和去除button点击时的默认背景色
2019-04-29
微信小程序——自定义组件
2019-04-29
js数组原型方法
2019-04-29
JavaScrip实现点击切换验证码及校验
2019-04-29
Java图形化绘制
2019-04-29
输入/输出流和文件操作
2019-04-29
Java数据库简介
2019-04-29
Java线程简介
2019-04-29
Java网络通信简介
2019-04-29
URL编程简介
2019-04-29
Java集合简介
2019-04-29
HTML5之Validation Plugin表单插件使用(仅供参考)
2019-04-29
HTML5简单轮播的实现(使用JQuery)
2019-04-29
MongoDB数据库安装
2019-04-29
MongoDB数据库安装完成之后的配置
2019-04-29
Mongo数据库使用
2019-04-29
弹性布局做导航
2019-04-29
使用setTimeout()实现setInterval()功能
2019-04-29
jQuery鼠标经过显示二级导航菜单(用less写的)
2019-04-29
canvas刮涂层抽奖
2019-04-29