新闻详情

新闻详情

首页 / 资讯中心 / 详情

DeepSeek LeetCode 120. 三角形最小路径和 Golang实现

发布时间:2026/9/29 9:57:44来源:尧图网络
DeepSeek    LeetCode 120. 三角形最小路径和 Golang实现
LeetCode 120. 三角形最小路径和Golang 实现思路动态规划自底向上从倒数第二行开始向上递推。对于位置 (i, j)只能从下一行的 (i1, j) 或 (i1, j1) 走上来triangle[i][j] min(triangle[i1][j], triangle[i1][j1])推到顶部后triangle[0][0] 就是最小路径和。Golang 实现一维 DP不修改原数组funcminimumTotal(triangle[][]int)int{n:len(triangle)ifn0{return0}// dp 初始化为最后一行的副本dp:make([]int,n)copy(dp,triangle[n-1])// 从倒数第二行向上遍历fori:n-2;i0;i--{forj:0;jlen(triangle[i]);j{// dp[j] triangle[i][j] min(dp[j], dp[j1])ifdp[j]dp[j1]{dp[j]triangle[i][j]dp[j]}else{dp[j]triangle[i][j]dp[j1]}}}returndp[0]}Golang 实现原地修改空间 O(1)funcminimumTotal(triangle[][]int)int{fori:len(triangle)-2;i0;i--{forj:0;jlen(triangle[i]);j{iftriangle[i1][j]triangle[i1][j1]{triangle[i][j]triangle[i1][j]}else{triangle[i][j]triangle[i1][j1]}}}returntriangle[0][0]}关键点自底向上避免处理边界和初始化最终直接返回顶部元素。状态转移dp[j] triangle[i][j] min(dp[j], dp[j1])。空间优化一维 dp 在计算当前行时只依赖下一行可原地覆盖。Go 注意· copy(dp, triangle[n-1]) 复制最后一行避免修改原数组。· dp[j] 和 dp[j1] 在更新 dp[j] 时dp[j1] 仍是下一行的值所以从前往后遍历即可。· 原地修改法不需要额外分配内存。复杂度· 时间O(n^2)n 为三角形行数每个元素访问一次。· 空间一维 DP 法 O(n)原地修改法 O(1)不计输入本身。测试用例funcTestMinimumTotal(t*testing.T){cases:[]struct{triangle[][]intwantint}{{[][]int{{2},{3,4},{6,5,7},{4,1,8,3}},11},{[][]int{{-10}},-10},{[][]int{{-1},{2,3},{1,-1,-3}},-1},}for_,c:rangecases{ifgot:minimumTotal(c.triangle);got!c.want{t.Errorf(minimumTotal(%v) %d, want %d,c.triangle,got,c.want)}}}
网站建设高端定制企业官网
RELATED

相关资讯

更多精彩内容,欢迎继续阅读

较早相关资讯

最新相关资讯

Spring Cloud Alibaba 全家桶实战:Nacos + Sentinel + Seata 微服务治理配置骨架与验证 2026/9/29 9:57:44

Spring Cloud Alibaba 全家桶实战:Nacos + Sentinel + Seata 微服务治理配置骨架与验证

/* MD / 富文本中的 .toc(含博客园搬家等嵌套结构);.toc-box 在侧栏,不受影响 */#content_views .toc,/* 编辑器常在目录前后插入空 p(:empty 仍占 20px),一并去掉避免顶空隙 */#content_views.markdown_views > p:empty:has(+ .toc),#content_views.markdown_views …

阅读更多 →
在Python编程生态中,动态求值(Dynamic Evaluation)是一项赋予代码极高灵活性的核心特性 2026/9/29 9:57:37

在Python编程生态中,动态求值(Dynamic Evaluation)是一项赋予代码极高灵活性的核心特性

在Python编程生态中,动态求值(Dynamic Evaluation)是一项赋予代码极高灵活性的核心特性。它允许程序在运行时将字符串形式的代码或表达式解析并执行,从而打破了传统静态编译语言的刚性限制。这种机制使得开发者能够构建高度可配置…

阅读更多 →
高效自动化测试脚本的十大最佳实践:从能跑到可维护 2026/9/29 9:57:37

高效自动化测试脚本的十大最佳实践:从能跑到可维护

做自动化测试这些年,我见过太多脚本项目从雄心勃勃走向静默弃坑。最典型的剧本是:团队定了个自动化率目标,几个人加班加点写脚本,前两个月确实跑得欢,可只要业务一改版,脚本就开始成片变红,修脚…

阅读更多 →
从零搭建灌装监控系统(八):断线检测与自动重连 2026/9/29 9:57:37

从零搭建灌装监控系统(八):断线检测与自动重连

断线检测与自动重连这是「从零搭建灌装监控系统」系列第8篇。上一篇实现了 200ms 轮询循环,但 PLC 断线后只是检测到断线,不会自动恢复。这篇实现自动重连机制——3次超时阈值判定断线、串口和TCP分别重连策略、重连间隔递增、重连成功后恢复轮询。让系统…

阅读更多 →
大模型推理加速:TensorRT-LLM与vLLM协同优化实战 2026/9/29 9:57:30

大模型推理加速:TensorRT-LLM与vLLM协同优化实战

1. 项目概述:Model-Optimizer 不是工具名,而是工程范式的代号“Model-Optimizer”这个标题乍看像某个开源工具或商业软件的名称,但结合NVIDIA、TensorRT-LLM、vLLM、PT文件转换、Docker镜像部署等高频热词,它实际指向的是一整套面…

阅读更多 →
安稳顺利毕业:6款2026年高效AI论文平台深度横评与TaoToken统一Key接入实践 2026/9/29 9:57:30

安稳顺利毕业:6款2026年高效AI论文平台深度横评与TaoToken统一Key接入实践

/* MD / 富文本中的 .toc(含博客园搬家等嵌套结构);.toc-box 在侧栏,不受影响 */#content_views .toc,/* 编辑器常在目录前后插入空 p(:empty 仍占 20px),一并去掉避免顶空隙 */#content_views.markdown_views > p:empty:has(+ .toc),#content_views.markdown_views …

阅读更多 →

今日资讯

本周资讯

本月资讯

看完文章仍有疑问?

联系尧图顾问,获取一对一建站咨询

立即免费咨询 📞 400-888-8888
📞 ✉