原题链接:http://oj.leetcode.com/problems/minimum-path-sum/这道题跟Unique
Paths,Unique
Paths II是相同类型的。事实上,这道题是上面两道题的general版本,是寻找带权重的path。在Unique
Paths中,我们假设每个格子权重都是1,而在Unique
Paths II中我们假设障碍格子的权重是无穷大,所以永远不会选择。剩下的区别就是这道题寻找这些路径中权重最小的,而不是总路径数。其实方法是一样的,还是使用动态规划,只是现在维护的不是路径数,而是到达某一个格子的最短路径(也就是权重之和最小)。而这个当前最短路径可以取前面一格和上面一格中小的最短路径长度得到,因此递推式是res[i][j]=min(res[i-1][j],
res[i][j-1])+grid[i][j]。总共进行两层循环,时间复杂度是O(m*n)。而空间复杂度仍是使用Unique
Paths中的方法来省去一维,是O(m),不了解的朋友可以看看哈。代码如下:public int minPathSum(int[][] grid) {
if(grid == null || grid.length==0 || grid[0].length==0)
return 0;
int[] res = new int[grid[0].length];
res[0] = grid[0][0];
for(int i=1;i<grid[0].length;i++)
{
res[i] = res[i-1]+grid[0][i];
}
for(int i=1;i<grid.length;i++)
{
for(int j=0;j<grid[0].length;j++)
{
if(j==0)
res[j] += grid[i][j];
else
res[j] = Math.min(res[j-1], res[j])+grid[i][j];
}
}
return res[grid[0].length-1];
}
这道题是动态规划的经典题型,模型足够简单,所以可能在简单的面试(比如电面)中出现。总体来说还是比较容易的,递推式比较直观。
分享到:
相关推荐
Algorithm-LeetCode-Sol-Res.zip,干净,易懂的解决方案和资源,为leetcode在线判断算法问题。,算法是为计算机程序高效、彻底地完成任务而创建的一组详细的准则。
cauly-rust-leetcode-utils={path="path/to/cauly-rust-leetcode-utils"} 使用来自 cauly-rust-leetcode-utils 的数据结构(“使用 cauly_rust_leetcode_utils::..”) 运行cargo run --manifest-path=path/to/cauly...
Algorithm-leetcode-spider.zip,leetcode公司,算法是为计算机程序高效、彻底地完成任务而创建的一组详细的准则。
~/.vscode/extensions/leetcode.vscode-leetcode-0.17.0/node_modules/vsc-leetcode-cli/bin/leetcode /usr/local/bin/leetcode 修改模板 open ~/.vscode/extensions/leetcode.vscode-leetcode-0.17.0/node_modules/...
leetcode-cli-plugins leetcode-cli 的第 3 方插件。 什么是 如何使用 如何使用 插件 名称 描述 增强的命令 按公司或标签过滤问题 list 不要在同一台计算机上使 Chrome 的会话过期 login 不要在同一台计算机上使 ...
主要介绍了LeetCode -- Path Sum III分析及实现方法的相关资料,希望通过本文能帮助到大家,需要的朋友可以参考下
Algorithm-LeetCode-Solution-From-GuaZiDou.zip,Leetcode解决方案Gitbook,算法是为计算机程序高效、彻底地完成任务而创建的一组详细的准则。
leetcode题库所有数据库问题 Leetcode 所有数据库问题:Leetcode 问题 Active-Businesses-LeetCode.png 活跃用户-LeetCode.png 活动-参与者-LeetCode.png 至少合作过三次的演员和导演-LeetCode.png Ads-Performance-...
Swif-LeetCode-Utils:在LeetCode上快速创建和打印ListNode和TreeNode的方式
RandomPickWithWeight-LeetCode-528-源码.rar
Leetcode-解决方案-CSharp ***此存储库将包含 C# 中许多 Leetcode 问题的解决方案 收集雨水 - Leetcode 42 (Hard) 文本对齐 - Leetcode 68(硬) 买卖股票的最佳时机 III - Leetcode 123 (Hard) 买卖股票的最佳时机 ...
《leetcode-solutions》,刷算法题,需要有一定的英文阅读能力。。。
leetcode-cheat 的发布 它是什么 ? 这是一个chrome 扩展,可以帮助您更高效地使用 leetcode。您可以从 重要: leetcode-cheat 现在只支持中文版。 也就是说不完全支持leetcode.com,但是你可以用leetcode-cn.com代替...
Java-Leetcode-杨辉三角
前端大厂最新面试题-leetcode-interview-ts.docx
leetcode-js-tdd leetcode 勇士的简单样板 如何使用 克隆这个 repo 在你的 vscode 中安装 配置扩展以使用 repo 中的problems文件夹 使用1.two-sum.js案例导出解决方案 module . exports = { // ignore: true, fn : ...
leetcode 答案 -leetcode- leetcode刷题指南 不只是答案 更多的是过程 更重要的是纠错的过程
leetcode-cli 注意:这个存储库是为了临时使用而分叉的。 注意:从 webbrowser 复制 cookie 并使用leetcode user -c可以临时修复不能。 一个享受 leetcode 的高效 cli 工具! 非常感谢 leetcode.com,一个非常棒的...
leetcode 答案Leetcode---数据库 我对 Leetcode 数据库问题的回答
Algorithm-LeetCode-NOTES.zip,利特码,算法是为计算机程序高效、彻底地完成任务而创建的一组详细的准则。