【数据结构与算法】动态规划——最小路径和(普通矩阵、三角形两题)
内容导读
互联网集市收集整理的这篇技术教程文章主要介绍了【数据结构与算法】动态规划——最小路径和(普通矩阵、三角形两题),小编现在分享给大家,供广大互联网技能从业者学习和参考。文章包含1574字,纯文字阅读大概需要3分钟。
内容图文
![【数据结构与算法】动态规划——最小路径和(普通矩阵、三角形两题)](/upload/InfoBanner/zyjiaocheng/1128/88c1f636fa404794a09a795dfdd9682d.jpg)
最小路径和
LeetCode:最小路径和
题目描述:
给定一个包含非负整数的 m x n 网格,请找出一条从左上角到右下角的路径,使得路径上的数字总和为最小。
说明:每次只能向下或者向右移动一步。
示例:
输入:
[
[1,3,1],
[1,5,1],
[4,2,1]
]
输出: 7
解释: 因为路径 1→3→1→1→1 的总和最小。
思想:
动态规划,可以用原数组作为dp数组
代码:
class Solution {
public int minPathSum(int[][] grid) {
int i=0,j=0;
for(i=0;i<grid.length;++i){
for(j=0;j<grid[0].length;++j){
if(i>0&&j>0){
grid[i][j]+= Math.min(grid[i-1][j],grid[i][j-1]);
}else{
grid[i][j]+= (i==0?0:grid[i-1][j]) + (j==0?0:grid[i][j-1]);
}
}
}
return grid[i-1][j-1];
}
}
三角形最小路径和
LeetCode:三角形最小路径和
题目描述:
给定一个三角形,找出自顶向下的最小路径和。每一步只能移动到下一行中相邻的结点上。
如果你可以只使用 O(n) 的额外空间(n 为三角形的总行数)来解决这个问题,那么你的算法会很加分。
示例:
例如给定三角形
[
[2],
[3,4],
[6,5,7],
[4,1,8,3]
]
自顶向下的最小路径和为 11(即,2 + 3 + 5 + 1 = 11)。
思想:
自底向上,修改dp数组
代码:
第一种方法:在原数组上修改。这样貌似效率不高。
class Solution {
public int minimumTotal(List<List<Integer>> triangle) {
for(int i=triangle.size()-2;i>=0;--i){
for(int j=0;j<i+1;++j){
triangle.get(i).set(j,triangle.get(i).get(j)+Math.min(triangle.get(i+1).get(j+1),triangle.get(i+1).get(j)));
}
}
return triangle.get(0).get(0);
}
}
第二种方法:设置dp数组,修改dp数组;注意这很巧妙,每一次修改都不会影响下次循环的判断;其次,每次循环,最后一个数都不会修改它,直到最后一轮,加上顶部的数,得到最终结果dp[0]。
class Solution {
public int minimumTotal(List<List<Integer>> triangle) {
int len = triangle.size();
int[] dp=new int[len];
for(int i=0;i<len;++i){
dp[i]=triangle.get(len-1).get(i);
}
for(int i=len-2;i>=0;--i){
for(int j=0;j<i+1;++j){
dp[j] = Math.min(dp[j],dp[j+1]) + triangle.get(i).get(j);
}
}
return dp[0];
}
}
原文:https://www.cnblogs.com/buptleida/p/12641541.html
内容总结
以上是互联网集市为您收集整理的【数据结构与算法】动态规划——最小路径和(普通矩阵、三角形两题)全部内容,希望文章能够帮你解决【数据结构与算法】动态规划——最小路径和(普通矩阵、三角形两题)所遇到的程序开发问题。 如果觉得互联网集市技术教程内容还不错,欢迎将互联网集市网站推荐给程序员好友。
内容备注
版权声明:本文内容由互联网用户自发贡献,该文观点与技术仅代表作者本人。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容, 请发送邮件至 gblab@vip.qq.com 举报,一经查实,本站将立刻删除。
内容手机端
扫描二维码推送至手机访问。