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输出路径,多了一个 / 去…...
50| 选数
#include <bits/stdc.h> using namespace std;int n, k, ans, sum; // ans 最终答案 const int N 23; int a[N]; bool st[N];bool isprime(int x) {if (x < 1) return false;for (int i 2; i < sqrt(x); i)if (x % i 0) return false;return true; }void dfs(…...
Python从入门到精通(第14章):迭代器与生成器
开头导语 这是本系列第14章。前面你已经用过很多次迭代器和生成器——for x in data 的背后是什么,map 返回的对象为什么不能下标访问,range 为什么不会占很多内存——这些问题的答案都在本章。通过亲手实现一个迭代器类,你会对 Python 迭代协议有清晰的认识,遇到相关错误…...
如何在单台电脑上实现4人同屏游戏?Nucleus Co-Op开源项目详解
如何在单台电脑上实现4人同屏游戏?Nucleus Co-Op开源项目详解 【免费下载链接】nucleuscoop Starts multiple instances of a game for split-screen multiplayer gaming! 项目地址: https://gitcode.com/gh_mirrors/nu/nucleuscoop 你是否曾想过,…...
利用Dify平台快速搭建InternLM2-Chat-1.8B智能应用
利用Dify平台快速搭建InternLM2-Chat-1.8B智能应用 你是不是也遇到过这种情况:好不容易在服务器上部署了一个像InternLM2-Chat-1.8B这样的开源大模型,感觉它能力挺强,但除了在命令行里一问一答,就不知道怎么把它变成一个真正能用…...
Bootstrap 下拉菜单:全面解析与应用指南
Bootstrap 下拉菜单:全面解析与应用指南 引言 Bootstrap 是一个流行的前端框架,它提供了丰富的组件和工具来帮助开发者快速构建响应式、美观的网页。其中,下拉菜单是 Bootstrap 中一个常用且重要的组件,它能够帮助用户在有限的空间…...
Linux性能优化之上下文切换
写在前面 上下文切换因为会导致消耗大量的CPU资源,导致CPU升高,所以上下文切换也是最常见的性能杀手之一。本文就一起来看下这部分内容吧。 1:基础内容介绍 1.1:什么是上下文切换? CPU在执行的时候需要两部分的内容…...
智能抢票系统:从技术实现到场景落地
智能抢票系统:从技术实现到场景落地 【免费下载链接】Automatic_ticket_purchase 大麦网抢票脚本 项目地址: https://gitcode.com/GitHub_Trending/au/Automatic_ticket_purchase 你是否曾遇到这样的场景:苦等数月的演唱会门票在开票瞬间售罄&…...
If、switch选择结构
if单选结构package 选择结构;import java.util.Scanner;public class If单选择结构 {public static void main(String[] args) {Scanner scanner new Scanner(System.in);System.out.println("请输入内容:");String sscanner.nextLine();//equals&#x…...
5个认知重构,收割你的补偿性Offer
春招反杀指南当别人还在为秋招失利懊悔时,聪明人已经完成了思维系统的彻底升级秋招的硝烟尚未散尽,春招的号角已经吹响。这不是简单的“第二轮机会”,而是认知层面的降维打击战。那些在秋招中凭借简历光环轻松通关的路径已然失效,…...
LVGL V8项目实战:手把手教你用CLion配置CMake,集成Gui Guider生成的UI文件(含避坑指南)
LVGL V8项目实战:CLion与CMake深度集成Gui Guider UI文件的完整指南 当你在嵌入式GUI开发中频繁往返于设计工具与代码编辑器之间时,是否经历过这样的困境:在Gui Guider中精心设计的界面,移植到LVGL项目后却遭遇编译错误、资源路径…...
