千家信息网

请输入关键字词

热门搜索排行

最新搜索排行

导航： 首页 > 互联网科技 >

golang刷leetcode技巧之如何求三角形最小路径和

发表于：2025-12-02 作者：千家信息网编辑
千家信息网最后更新 2025年12月02日，这篇文章给大家分享的是有关golang刷leetcode技巧之如何求三角形最小路径和的内容。小编觉得挺实用的，因此分享给大家做个参考，一起跟随小编过来看看吧。三角形最小路径和给定一个三角形，找出自顶向
千家信息网最后更新 2025年12月02日golang刷leetcode技巧之如何求三角形最小路径和

这篇文章给大家分享的是有关golang刷leetcode技巧之如何求三角形最小路径和的内容。小编觉得挺实用的，因此分享给大家做个参考，一起跟随小编过来看看吧。

三角形最小路径和

给定一个三角形，找出自顶向下的最小路径和。每一步只能移动到下一行中相邻的结点上。

相邻的结点 在这里指的是 下标 与 上一层结点下标 相同或者等于 上一层结点下标 + 1 的两个结点。

例如，给定三角形：

[
     [2],
    [3,4],
   [6,5,7],
  [4,1,8,3]
]

自顶向下的最小路径和为 11（即，2 + 3 + 5 + 1 = 11）。

说明：

如果你可以只使用 O(n) 的额外空间（n 为三角形的总行数）来解决这个问题，那么你的算法会很加分。

解题思路：

1，对于位置［i，j］我们选［i+1，j]还是［i+1,j+1]取决于

sum(i+1,j)和sum（i+1,j+1)

2,递归可以解决，但是不是最优

3，动态规划

A,第i行依赖于第i＋1行，所以我们倒着来dp[i][j]=min(dp[i+1][j],dp[i+1][j+1])+triangle[i][j]

B，为了减少空间复杂度，我们第i行结果直接覆盖第i+1 行

代码实现：1递归

func minimumTotal(triangle [][]int) int {    if len(triangle)<1 || len(triangle[0])<1{        return 0    }
    sum:=triangle[0][0]    sum+=min(triangle,1,0)    return sum}
func min(a[][]int,i,j int)(int){    if i>=len(a) {        return 0    }    a0:=min(a,i+1,j)    a1:=min(a,i+1,j+1)    if a[i][j]+a0        return a[i][j]+a0    }    return a[i][j+1]+a1}

代码实现：2动态规划

func minimumTotal(triangle [][]int) int {    if len(triangle)<1 || len(triangle[0])<1{        return 0    }    l:=len(triangle[len(triangle)-1])    dp:=make([]int,l)    for i:=0;i        dp[i]=triangle[len(triangle)-1][i]    }        for i:=len(triangle)-2;i>=0;i--{        for j:=0;j            if dp[j]               dp[j]+=triangle[i][j]               }else{                dp[j]=dp[j+1]+triangle[i][j]               }        }    }    return dp[0]}

感谢各位的阅读！关于"golang刷leetcode技巧之如何求三角形最小路径和"这篇文章就分享到这里了，希望以上内容可以对大家有一定的帮助，让大家可以学到更多知识，如果觉得文章不错，可以把它分享出去让更多的人看到吧！

很赞哦！
三角形 三角 最小 路径 结点 下标 技巧 自顶向下 代码 内容 动态 更多 空间 篇文章 上一 递归 规划 不错 复杂 实用 数据库的安全要保护哪些东西 数据库安全各自的含义是什么 生产安全数据库录入 数据库的安全性及管理 数据库安全策略包含哪些 海淀数据库安全审计系统 建立农村房屋安全信息数据库 易用的数据库客户端支持安全管理 连接数据库失败ssl安全错误 数据库的锁怎样保障安全 行业网络安全应急队伍建设 长岛安卓软件开发哪家好 铜仁精益管理软件开发 vb数据库电除尘 关于网络安全威胁发展趋势 网络安全感悟题目 网络安全整改软硬件 广州市格利网络技术有限公司 mc服务器关闭禁水 浙江工程软件开发价格大全 全球网络安全协会 日照企业党建软件开发电话 奉贤区上门软件开发价钱 南华大学的网络安全实验室 北京中仪网络技术 数据库的访问技术包括 图片服务器搭建 中兴软件开发和软件测试比例 购买网络技术开发价目表 服务器安全软件哪个好用 单片机软件开发怎么样 有网络安全就没有国家安全人 易语言 sql添加数据库 软件开发+坑 access数据库表结构 优化系统数据库 网络安全在职学校 PC软件开发 知乎 中兴软件开发和软件测试比例 佛山卫星软件开发回收价

相关文章

0