千家信息网

请输入关键字词

热门搜索排行

最新搜索排行

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

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

发表于：2026-11-03 作者：千家信息网编辑
千家信息网最后更新 2026年11月03日，这篇文章给大家分享的是有关golang刷leetcode技巧之如何求三角形最小路径和的内容。小编觉得挺实用的，因此分享给大家做个参考，一起跟随小编过来看看吧。三角形最小路径和给定一个三角形，找出自顶向
千家信息网最后更新 2026年11月03日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安全错误 数据库的锁怎样保障安全 保险科技 互联网保险 科技与互联网 互联网科技财经 互联网与未来科技 广西互联网科技公司 狮子座互联网科技培训 互联网科技汛 云创客互联网科技公司 互联网时代科技改变生活 互联网大会黑科技排名 世界互联网科技公司市值排名 呼和浩特新华互联网科技学院 亳州好赞互联网科技有限公司 民营互联网公司国防科技 深圳市罗太互联网科技有限公司 特约风豹互联网科技为什么扣费 南通创西澳互联网科技有限公司 江苏互联网智能科技软件 广州燕处互联网科技有限公司 互联网领先科技成果宣传视频 互联网科技财经 喔噻互联网科技 茂名市互联网科技产业园 移动互联网年度科技创新 国大互联网教育科技有限公司工作 互联网科技大赛获奖感言 浙南科技城互联网大厦招聘 宇信科技在杭州互联网排第几 工业互联网科技创业 互联网时代高科技布局

相关文章

0