Leetcode 三角形最小路径和

算法思想与代码详解
这段代码采用的是**动态规划(Dynamic Programming)**的思想,用来解决“120. 三角形最小路径和”问题。动态规划通过将问题分解成更小的子问题,并通过保存子问题的解来避免重复计算,从而提高效率。
算法核心思路
-
从底向上计算(Bottom-Up Approach):
- 因为我们要求从顶点到底边的最小路径和,可以从底边开始,逐步向上计算每一层的最优解。
- 每个位置的最小路径和,取决于当前值和下一层两个可能的相邻路径值中的较小者。
-
状态表示(DP数组):
- 使用一个一维数组
dp来保存“从当前层到底边的最小路径和”。 dp[j]表示从当前层位置j到底边的最小路径和。
- 使用一个一维数组
-
状态转移方程:
- 对于某一层的节点
triangle[i][j],它的最小路径和为:
[
dp[j] = \min(dp[j], dp[j + 1]) + triangle[i][j]
] dp[j]表示当前位置j往下的最小路径,dp[j+1]表示下一个位置j+1往下的最小路径。
- 对于某一层的节点
-
最终结果:
- 计算完成后,
dp[0]即为从三角形顶点到底边的最小路径和。
- 计算完成后,
代码解读
public int minimumTotal(List<List<Integer>> triangle) {int n = triangle.size(); // 三角形的层数int[] dp = new int[n]; // 用一维数组保存动态规划结果// 初始化:将 dp 数组赋值为最后一层的值for (int i = 0; i < n; i++) {dp[i] = triangle.get(n - 1).get(i);}// 从倒数第二层开始,向上计算每层的最小路径和for (int i = n - 2; i >= 0; i--) {for (int j = 0; j <= i; j++) {// 动态规划状态转移:当前点的最小路径和dp[j] = Math.min(dp[j], dp[j + 1]) + triangle.get(i).get(j);}}// 最终答案存储在 dp[0]return dp[0];
}
运行流程
以输入 triangle = [[2], [3, 4], [6, 5, 7], [4, 1, 8, 3]] 为例:
-
初始化:
- 将最后一层
[4, 1, 8, 3]赋值到dp数组中:
[
dp = [4, 1, 8, 3]
]
- 将最后一层
-
从倒数第二层开始计算:
-
第 3 层 (
[6, 5, 7]):- ( dp[0] = \min(4, 1) + 6 = 7 )
- ( dp[1] = \min(1, 8) + 5 = 6 )
- ( dp[2] = \min(8, 3) + 7 = 10 )
更新后:
[
dp = [7, 6, 10, 3]
]
-
第 2 层 (
[3, 4]):- ( dp[0] = \min(7, 6) + 3 = 9 )
- ( dp[1] = \min(6, 10) + 4 = 10 )
更新后:
[
dp = [9, 10, 10, 3]
]
-
第 1 层 (
[2]):- ( dp[0] = \min(9, 10) + 2 = 11 )
更新后:
[
dp = [11, 10, 10, 3]
]
- ( dp[0] = \min(9, 10) + 2 = 11 )
-
-
最终结果:
- 返回
dp[0],即最小路径和为11。
- 返回
时间和空间复杂度
-
时间复杂度:
- 外层循环从底层到顶层,共 (n-1) 次。
- 内层循环每层最多运行 (i+1) 次,整体为 (O(n^2))。
- 总时间复杂度: (O(n^2))。
-
空间复杂度:
- 使用了一个一维数组
dp,大小为 (n)。 - 总空间复杂度: (O(n))。
- 使用了一个一维数组
总结
这段代码通过动态规划的思想,从底向上逐层计算路径和,用一个一维数组优化了空间开销,避免了重复计算,具有较高的效率,适用于求解此类逐层递归累加的问题。
java 实现
class Solution {public int minimumTotal(List<List<Integer>> triangle) {int n = triangle.size();int[] dp = new int[n];for(int i = 0; i < n; i++) {dp[i] = triangle.get(n - 1).get(i);}for(int i = n - 2; i >= 0; i--) { // i 自底向上for(int j = 0; j <= i; j++) { // j 对当前行从左到右遍历, 当 j == i 时,该行的dp[i]值得以确定dp[j] = Math.min(dp[j], dp[j + 1]) + triangle.get(i).get(j);}}return dp[0];}
}
相关文章:
Leetcode 三角形最小路径和
算法思想与代码详解 这段代码采用的是**动态规划(Dynamic Programming)**的思想,用来解决“120. 三角形最小路径和”问题。动态规划通过将问题分解成更小的子问题,并通过保存子问题的解来避免重复计算,从而提高效率。…...
DataOps驱动数据集成创新:Apache DolphinScheduler SeaTunnel on Amazon Web Services
引言 在数字化转型的浪潮中,数据已成为企业最宝贵的资产之一。DataOps作为一种文化、流程和实践的集合,旨在提高数据管道的质量和效率,从而加速数据从源头到消费的过程。白鲸开源科技,作为DataOps领域的领先开源原生公司…...
Android Studio的笔记--BusyBox相关
BusyBox 相关 BusyBoxandroid上安装busybox和使用示例一、下载二、移动三、安装和设置环境变量四、使用 busybox源码下载和查看 BusyBox BUSYBOX BUSYBOX链接https://busybox.net/ 点击链接后如图 点击左边菜单栏的Get BusyBix中的Download Source 跳转到busybox 的下载源码…...
MySQL 存储过程与函数:增强数据库功能
一、MySQL 存储过程与函数概述 (一)存储过程的定义与特点 存储过程是一组预编译的 SQL 语句集合,它们被存储在数据库中,可根据需要被重复调用。例如,在一个电商系统中,经常需要查询某个时间段内的订单数据…...
网络安全(3)_安全套接字层SSL
4. 安全套接字层 4.1 安全套接字层(SSL)和传输层安全(TLS) (1)SSL/TLS提供的安全服务 ①SSL服务器鉴别,允许用户证实服务器的身份。支持SSL的客户端通过验证来自服务器的证书,来鉴别…...
Git 快速入门
Git 是什么? Git 是一个分布式版本控制系统四大区域: 工作区:项目文件的当前状态,即本地目录。暂存区:保存将要提交的文件快照,是一个中间层,使用git add将文件添加到暂存区。本地仓库…...
AI学习记录 - 依据 minimind 项目入门
想学习AI,还是需要从头到尾跑一边流程,最近看到这个项目 minimind, 我也记录下学习到的东西,需要结合项目的readme看。 1、github链接 https://github.com/jingyaogong/minimind?tabreadme-ov-file 2、硬件环境:英伟达4070ti …...
数据结构----链表头插中插尾插
一、链表的基本概念 链表是一种线性数据结构,它由一系列节点组成。每个节点包含两个主要部分: 数据域:用于存储数据元素,可以是任何类型的数据,如整数、字符、结构体等。指针域:用于存储下一个节点&#…...
设计模式-读书笔记
确认好: 模式名称 问题:在何时使用模式,包含设计中存在的问题以及问题存在的原因 解决方案:设计模式的组成部分,以及这些组成部分之间的相互关系,各自的职责和协作方式,用uml类图和核心代码描…...
c语言----选择结构
基本概念 选择结构是C语言中用于根据条件判断来执行不同代码块的结构。它允许程序在不同的条件下执行不同的操作,使程序具有决策能力。 if语句 单分支if语句 语法格式: if (条件表达式) { 执行语句块; } 功能: 当条件表达式的值为真&#…...
KS曲线python实现
目录 实战 实战 # 导入第三方模块 import pandas as pd import numpy as np import matplotlib.pyplot as plt# 自定义绘制ks曲线的函数 def plot_ks(y_test, y_score, positive_flag):# 对y_test重新设置索引y_test.index np.arange(len(y_test))# 构建目标数据集target_dat…...
解决matplotlib中文乱码问题
进入python,查看缓存 import matplotlib as mpl print(mpl.get_cachedir())如果结果为/Users/xxx/.matplotlib 那么就rm -rf /Users/xxx/.matplotlib 然后 mkdir ~/.fonts cd ~/.fonts wget http://129.204.205.246/downloads/SimHei.ttfsudo apt-get install fo…...
实操给桌面机器人加上超拟人音色
前面我们讲了怎么用CSK6大模型开发板做一个桌面机器人充当AI语音助理,近期上线超拟人方案,不仅大模型语音最快可以1秒内回复,还可以让我们的桌面机器人使用超拟人音色、具备声纹识别等能力,本文以csk6大模型开发板为例实操怎么把超…...
git stash 的文件如何找回
在Git中,如果你使用了git stash命令来保存你的工作进度,但之后想要找回这些被stash的文件,你可以按照以下步骤进行操作: 1. 查看stash列表 首先,使用git stash list命令来查看当前保存的所有stash记录。这个命令会列出…...
皮肤伤口分割数据集labelme格式248张5类别
数据集格式:labelme格式(不包含mask文件,仅仅包含jpg图片和对应的json文件) 图片数量(jpg文件个数):284 标注数量(json文件个数):284 标注类别数:5 标注类别名称:["bruises","burns","cu…...
uni-app开发AI康复锻炼小程序,帮助肢体受伤患者康复!
**提要:**近段时间我们收到多个康复机构用户,咨询AI运动识别插件是否可以应用于肢力运动受限患者的康复锻炼中来,插件是可以应用到AI康复锻炼中的,今天小编就为您介绍一下AI运动识别插件在康腹锻炼中的应用场景。 一、康复机构的应…...
双内核架构 Xenomai 4 安装教程
Xenomai 4是一种双内核架构, 继承了Xenomai系列的特点,通过在Linux内核中嵌入一个辅助核心(companion core),来提供实时能力。这个辅助核心专门处理那些需要极低且有界响应时间的任务。 本文将在官网教程(https://evlproject.org/…...
【redis的使用、账号流程、游戏服Handler的反射调用】1.自增id 2.全局用户名这样子名字唯一 3.
一、web服 1)账号注册 // 用于唯一命名服务 com.xinyue.game.center.business.account.logic.AccountRegisterService#accountRegister public void accountRegister(AccountEntity account) {accountManager.checkUsername(account.getUsername());accountManager.checkPass…...
neo4j 图表数据导入到 TuGraph
neo4j 图表数据导入到 TuGraph 代码文件说明后文 前言:近期在引入阿里的 TuGraph 图数据库,需要将 原 neo4j 数据导入到新的 tugraph 数据库中。预期走csv文件导入导出,但因为格式和数据库设计问题,操作起来比较麻烦(可能是个人没…...
启动报错java.lang.NoClassDefFoundError: ch/qos/logback/core/status/WarnStatus
报错信息图片 日志: Exception in thread "Quartz Scheduler [scheduler]" java.lang.NoClassDefFoundError: ch/qos/logback/core/status/WarnStatus先说我自己遇到的问题,我们项目在web设置了自定义的log输出路径,多了一个 / 去…...
零门槛NAS搭建:WinNAS如何让普通电脑秒变私有云?
一、核心优势:专为Windows用户设计的极简NAS WinNAS由深圳耘想存储科技开发,是一款收费低廉但功能全面的Windows NAS工具,主打“无学习成本部署” 。与其他NAS软件相比,其优势在于: 无需硬件改造:将任意W…...
visual studio 2022更改主题为深色
visual studio 2022更改主题为深色 点击visual studio 上方的 工具-> 选项 在选项窗口中,选择 环境 -> 常规 ,将其中的颜色主题改成深色 点击确定,更改完成...
macOS多出来了:Google云端硬盘、YouTube、表格、幻灯片、Gmail、Google文档等应用
文章目录 问题现象问题原因解决办法 问题现象 macOS启动台(Launchpad)多出来了:Google云端硬盘、YouTube、表格、幻灯片、Gmail、Google文档等应用。 问题原因 很明显,都是Google家的办公全家桶。这些应用并不是通过独立安装的…...
Cloudflare 从 Nginx 到 Pingora:性能、效率与安全的全面升级
在互联网的快速发展中,高性能、高效率和高安全性的网络服务成为了各大互联网基础设施提供商的核心追求。Cloudflare 作为全球领先的互联网安全和基础设施公司,近期做出了一个重大技术决策:弃用长期使用的 Nginx,转而采用其内部开发…...
三体问题详解
从物理学角度,三体问题之所以不稳定,是因为三个天体在万有引力作用下相互作用,形成一个非线性耦合系统。我们可以从牛顿经典力学出发,列出具体的运动方程,并说明为何这个系统本质上是混沌的,无法得到一般解…...
学习STC51单片机32(芯片为STC89C52RCRC)OLED显示屏2
每日一言 今天的每一份坚持,都是在为未来积攒底气。 案例:OLED显示一个A 这边观察到一个点,怎么雪花了就是都是乱七八糟的占满了屏幕。。 解释 : 如果代码里信号切换太快(比如 SDA 刚变,SCL 立刻变&#…...
大数据学习(132)-HIve数据分析
🍋🍋大数据学习🍋🍋 🔥系列专栏: 👑哲学语录: 用力所能及,改变世界。 💖如果觉得博主的文章还不错的话,请点赞👍收藏⭐️留言Ǵ…...
九天毕昇深度学习平台 | 如何安装库?
pip install 库名 -i https://pypi.tuna.tsinghua.edu.cn/simple --user 举个例子: 报错 ModuleNotFoundError: No module named torch 那么我需要安装 torch pip install torch -i https://pypi.tuna.tsinghua.edu.cn/simple --user pip install 库名&#x…...
CSS设置元素的宽度根据其内容自动调整
width: fit-content 是 CSS 中的一个属性值,用于设置元素的宽度根据其内容自动调整,确保宽度刚好容纳内容而不会超出。 效果对比 默认情况(width: auto): 块级元素(如 <div>)会占满父容器…...
算法:模拟
1.替换所有的问号 1576. 替换所有的问号 - 力扣(LeetCode) 遍历字符串:通过外层循环逐一检查每个字符。遇到 ? 时处理: 内层循环遍历小写字母(a 到 z)。对每个字母检查是否满足: 与…...
