【每日一题】给定一个包含非负整数的 m x n 网格,请找出一条从左上角到右下角的路径,使得路径上的数字总和为最小。 说明:每次只能向下或者向右移动一步。
发布日期:2021-10-06 02:38:42
浏览次数:5
分类:技术文章
本文共 1067 字,大约阅读时间需要 3 分钟。
给定一个包含非负整数的 m x n 网格,请找出一条从左上角到右下角的路径,使得路径上的数字总和为最小。
说明:每次只能向下或者向右移动一步。
示例:
输入:
[ [1,3,1], [1,5,1], [4,2,1] ] 输出: 7 解释: 因为路径 1→3→1→1→1 的总和最小。class Solution { public int minPathSum(int[][] grid) { int[][] dp= new int[grid.length][grid[0].length]; for(int i =0; i< grid.length; i++){ int temp = i==0?0:dp[i-1][0]; dp[i][0] = grid[i][0] + temp; } for(int j=0; j< grid[0].length; j++){ int temp = j==0?0:dp[0][j-1]; dp[0][j] = grid[0][j] + temp; } for(int i= 1; i< grid.length; i++){ for(int j= 1; j< grid[0].length; j++){ int iTemp = grid[i][j] + dp[i-1][j]; int jTemp = grid[i][j] + dp[i][j-1]; dp[i][j] = iTemp > jTemp ? jTemp:iTemp; } } return dp[grid.length-1][grid[0].length-1]; }}
时间复杂度:O(mn)O(mn),其中 mm 和 nn 分别是网格的行数和列数。需要对整个网格遍历一次,计算 \textit{dp}dp 的每个元素的值。
空间复杂度:O(mn)O(mn),其中 mm 和 nn 分别是网格的行数和列数。创建一个二维数组 dpdp,和网格大小相同。
空间复杂度可以优化,例如每次只存储上一行的 \textit{dp}dp 值,则可以将空间复杂度优化到 O(n)O(n)。转载地址:https://blog.csdn.net/luxuiary/article/details/107531897 如侵犯您的版权,请留言回复原文章的地址,我们会给您删除此文章,给您带来不便请您谅解!
发表评论
最新留言
不错!
[***.144.177.141]2024年04月02日 13时57分39秒
关于作者
喝酒易醉,品茶养心,人生如梦,品茶悟道,何以解忧?唯有杜康!
-- 愿君每日到此一游!
推荐文章
移动2020面试题:斗地主
2019-04-26
MySQL 表锁、行锁、间隙锁、页锁介绍分析
2019-04-26
codeforces 789A(数学)
2019-04-26
Codeforces 796A
2019-04-26
dp46上 HDU2084
2019-04-26
dp46上 HDU1421
2019-04-26
UESTC 1324线段树
2019-04-26
POJ1651 区间dp
2019-04-26
spfa、Dijkstra、Floyd算法最短路算法详解
2019-04-26
HDU4725(spfa+双端队列优化)
2019-04-26
PowerOj 2392(树状数组 or CDQ分治)
2019-04-26
HDU 6119(区间交叉问题)
2019-04-26
hdu 6143(精妙的递推)
2019-04-26
数位dp
2019-04-26
Power oj 2540 (FFT卷积)
2019-04-26
hdu 6165(dfs or bfs or tarjan+topsort)
2019-04-26
hdu 6168(stl)
2019-04-26
hdu 6170(正则表达式)
2019-04-26
排列组合 "n个球放入m个盒子m"问题 总结(转)
2019-04-26