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. 三角形最小路径和”问题。动态规划通过将问题分解成更小的子问题,并通过保存子问题的解来避免重复计算,从而提高效率。…...
[Unity]Unity跨平台开发之Android入门
安卓环境配置 安装依赖项 推荐使用Unity Hub进行安装,安装时勾选Android Build Support、Android SDK & NDK Tools、OpenJDK。或者指定已安装的依赖项。(注意:指定的依赖项需要是从UnityHub安装的。比如之前安装Unity2022时勾选了上述依…...
搭建Flume
title: 搭建Flume date: 2024-11-30 23:59:00 categories: - 服务器 tags: - Flume - 大数据搭建Flume 本次实验环境:Centos 7-2009、JDK 8、Flume-1.11.0 开始安装 1. 下载安装文件到服务器 # 使用wget命令下载flume文件(二选一) wget …...
【从零开始入门unity游戏开发之——C#篇10】循环结构——while、do-while、for、foreach的使用
文章目录 一、while 循环1、语法:2、示例: 二、 do-while 循环1、语法:2、示例: 三、for 循环1、语法:2、示例: 四、foreach 循环1、语法:2、示例: 五、总结对比六、注意事项七、使用…...
flask flask-socketio创建一个网页聊天应用
应用所需环境: python 3.11.11 其他 只需要通过这个命令即可 pip install flask3.1.0 Flask-SocketIO5.4.1 -i https://mirrors.tuna.tsinghua.edu.cn/pypi/web/simple 最好是用conda创建一个新的虚拟环境来验证 完整的pip list如下 Package Version ----…...
MVCC了解
MVCC(多版本并发控制)学习指南及代码示例 一、学习MVCC前先了解什么 1. MVCC的定义和作用 MVCC是一种并发控制机制,用于解决并发事务访问数据库时可能出现的问题,如脏读、不可重复读和幻读。它通过为每个数据行维护多个版本来实…...
LabVIEW随机扫描成像系统
利用LabVIEW开发了一套随机扫描成像系统,利用硬件时钟实现声光偏转器(AOD)的频率控制与信号采集之间的高速时间同步。系统利用了高精度的时钟同步技术,确保了成像精度和重复性,从而有效提高了成像速度和质量。 项目背景…...
系统移植——Linux 内核顶层 Makefile 详解
一、概述 Linux Kernel网上下载的版本很多NXP等有自己对应的版本。需要从网上直接下载就可以。 二、Linux内核初次编译 编译内核之前需要先在 ubuntu 上安装 lzop 库 sudo apt-get install lzop 在 Ubuntu 中 新 建 名 为 “ alientek_linux ” 的 文 件夹 , …...
【一文了解】C#重点-委托1
本篇文章来学习一下C#的委托,委托是C#中的一个重要概念,它允许将方法作为参数传递给其他方法。C#中的委托类似于C或C中的函数指针,并且类型安全。 委托 1.委托的定义 委托(delegate)是方法的代理/代表,委托…...
LeetCode hot100-87
https://leetcode.cn/problems/longest-increasing-subsequence/?envTypestudy-plan-v2&envIdtop-100-liked 300. 最长递增子序列 已解答 中等 相关标签 相关企业 给你一个整数数组 nums ,找到其中最长严格递增子序列的长度。子序列 是由数组派生而来的序列&a…...
项目26:简易在线论坛 --- 《跟着小王学Python·新手》
项目26:简易在线论坛 — 《跟着小王学Python新手》 《跟着小王学Python》 是一套精心设计的Python学习教程,适合各个层次的学习者。本教程从基础语法入手,逐步深入到高级应用,以实例驱动的方式,帮助学习者逐步掌握Pyth…...
知乎 PB 级别 TiDB 数据库集群管控实践
以下文章来源于知乎技术专栏 ,作者代晓磊 导读 在现代企业中,数据库的运维管理至关重要,特别是面对分布式数据库的复杂性和大规模集群的挑战。作为一款兼容 MySQL 协议的分布式关系型数据库,TiDB 在高可用、高扩展性和强一致性方…...
Intel(R) Iris(R) Xe Graphics安装Anaconda、Pytorch(CPU版本)
一、Intel(R) Iris(R) Xe Graphics安装Anaconda 下载网址:https://repo.anaconda.com/archive/ 双击Anaconda3-2024.10-1-Windows-x86_64,一直下一步,选择安装的路径位置,一直下一步就安装完成了。打开Anaconda PowerShell Promp…...
RK3588 , mpp硬编码rgb, 保存MP4视频文件.
RK3588 , mpp硬编码yuv, 保存MP4视频文件. ⚡️ 传送 ➡️ RK3588, FFmpeg 拉流 RTSP, mpp 硬解码转RGBRk3588 FFmpeg 拉流 RTSP, 硬解码转RGBUbuntu x64 架构, 交叉编译aarch64 FFmpeg mppCode Init MppMPP_RET init_mpp...
揭开 Choerodon UI 拖拽功能的神秘面纱
01 引言 系统的交互方式主要由点击、选择等组成。为了提升 HZERO 系统的用户体验、减少部分操作步骤,组件库集成了卓越的拖拽功能,让用户可以更高效流畅的操作系统。 例如:表格支持多行拖拽排序、跨表数据调整、个性化调整列顺序࿱…...
常用网络协议简述
网络协议是计算机网络中规定数据交换格式和交换规则的一套标准。以下是一些常用的网络协议及其简要解释: HTTP(HyperText Transfer Protocol,超文本传输协议) 用于从网络传输超文本数据到本地浏览器的传输协议。基于TCP协议&…...
本地电脑使用命令行上传文件至远程服务器
将本地文件上传到远程服务器,在本地电脑中cmd使用该命令: scp C:/Users/"你的用户名"/Desktop/environment.yml ws:~/environment.yml 其中,C:/Users/“你的用户名”/Desktop/environment.yml是本地文件的路径, ~/en…...
笔记day2
文章目录 1 NavigationDuplivated警告错误2 Home模块组件拆分3 三级联动组件完成4 完成其余静态组件5 POSTMAN测试接口6 axios二次封装6.1 为什么需要进行二次封装axios?6.2 在项目中经常API文件夹【axios】6.3 axios基础不好,可以参考git|NPM关于axios文…...
排序算法(3)——归并排序、计数排序
目录 1. 归并排序 1.1 递归实现 1.2 非递归实现 1.3 归并排序特性总结 2. 计数排序 代码实现 3. 总结 1. 归并排序 基本思想: 归并排序(merge sort)是建立在归并操作上的一种有效的排序算法,该算法是采用分治法࿰…...
【5】C#期末复习第5套
1.int a[3][2]{2,4,6,8,10.12};则*(a[1]1)的值是8 指向(a[1]的第二个元素) 再* 2.合并字符串库函数strcat 3.比较字符串库函数strcmp 4.执行结果是x3,y3 int x3,y; int *px&x; y*px; (优先级高于*) 5.*p[5]没…...
jquery虚拟键盘插件jqkeyboard
jqKeyboard是一款jquery虚拟键盘插件。该虚拟键盘插件依赖于jquery ui,通过该插件,可以在页面中生成一个扁平风格的虚拟键盘面板。 在线预览 下载 安装 可以通过npm来安装jqKeyboard虚拟键盘插件。 npm install jq keyboard --save 使用方法 在页面…...
IMX6ULL开发板把屏幕刷黑(黑屏)的程序
承接博文 IMX6ULL开发板基础实验:Framebuffer驱动程序的简单应用实例代码详细分析 很容易写出把屏幕刷黑的程序… Ubuntu中的目录/home/book/mycode下新建目录C0003_draw_lcd_black,然后把把博文中的源码/home/book/mycode/C0002_show_pixel复制到目录C0003_draw_l…...
OpenCV基本图像处理操作(三)——图像轮廓
轮廓 cv2.findContours(img,mode,method) mode:轮廓检索模式 RETR_EXTERNAL :只检索最外面的轮廓;RETR_LIST:检索所有的轮廓,并将其保存到一条链表当中;RETR_CCOMP:检索所有的轮廓,并将他们组…...
C语言学习day24:DLL给程序打上窗口破解补丁
简言 在上一章节我们知道了DLL,编写DLL以及最重要的导出DLL,这一章节我们学习如何给应用打上窗口破解补丁(DLL)。 流程 工具:studyPE 操作: 把要补丁的程序拖入PE中点击导入菜单,导入dll函…...
大模型呼出机器人的应用场景
大模型呼出机器人的应用场景 原作者:开源呼叫中心FreeIPCC,其Github:https://github.com/lihaiya/freeipcc 大模型呼出机器人的应用场景十分广泛,涵盖了多个行业和服务领域。以下是对其应用场景的详细归纳: 一、客户…...
el-date-picker筛选时间日期选择范围
el-date-picker 选择时间日期范围-> 昨天 近7天 30天<template><div class"main"><div class"header"><el-form :model"form" label-width"auto"><el-button plain click"setTimeToYesterday&q…...
【Apache Paimon】-- 10 -- Paimon 0.9.0 集成 Hive 3.1.3
参考官方 0.9.0 版本文档:https://paimon.apache.org/docs/0.9/engines/hive/ 1、下载依赖包到 hive lib 下 $ cd $HIVE_HOME/$ mkdir auxlib$ cd auxlib$ wget https://repo.maven.apache.org/maven2/org/apache/paimon/paimon-hive-connector-3.1/0.9.0/paimon-hive-connec…...
vue2如何写一个轮播图
需求描述 写一个轮播图,可以实现如下效果: 页面上展示三个轮播图元素默认状态下,进行自动轮播,循环播放一旦鼠标移入轮播图范围内,并停留在元素a上,则轮播图停止自动播放,同时将元素a放大 核…...
基础库httpx的使用
urllib 库和 requests 库的使用,已经可以爬取绝大多数网站的数据,但对于某些网站依然无能为力。什么情况?这些网站强制使用HTTP/2.0协议访问,这时 urllib 和requests 是无法爬取数据的,因为它们只支持 HTTP/1.1,不支持…...
MYSQL 利用concat函数 生成更新或者插入SQL
有时候需要批量运维一批数据,一条一条写SQL比较麻烦,可以使用下面的方法批量生成select sales_order_number,a.sog_line_id,actual_price,sales_goods_unit_price,b.id,concat(update your_table set actual_price, sales_goods_unit_price, where id,b…...
Backend For Frontend的学习分享
晚上公司开了一个技术分享会,主要内容就是公司的项目架构,会中讲解了项目整体架构是BFF架构,就是在微服务之上多加了一层。 除此之外,还讲解了DDD设计思想,主要用于各个业务中台,如订单中台、用户中台等。…...
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…...
【GO环境安装】mac系统+GoLand使用
文章目录 下载安装包环境配置GoLandGo Modules 下载安装包 地址:GO下载地址 下载好后直接进行安装: 进入terminal,查看是否安装成功: 环境配置 在文稿下面创建工作目录: 在文稿下新建Go_Works文件夹,在…...
2025年入职/转行网络安全,该如何规划?网络安全职业规划
网络安全是一个日益增长的行业,对于打算进入或转行进入该领域的人来说,制定一个清晰且系统的职业规划非常重要。2025年,网络安全领域将继续发展并面临新的挑战,包括不断变化的技术、法规要求以及日益复杂的威胁环境。以下是一个关…...
linux中 umask 命令
Umask Umask(User File Creation Mode Mask)是Linux系统中的一项命令,用于设定新创建文件和目录的默认权限。 一、umask的作用 Umask通过掩码操作,限制新文件和目录的访问权限。在Linux中,所有的文件和目录都被分配…...
OpenCV函数及其应用
1. 梯度处理的Sobel算子函数 功能 Sobel算子是一种用于边缘检测的离散微分算子,它结合了高斯平滑和微分求导,用于计算图像亮度的空间梯度。 参数 src:输入图像。 dst:输出图像。 ddepth:输出图像的深度。 dxÿ…...
使用ENSP实现NAT(2)
一、NAT的类型 二、静态NAT 1.项目拓扑 2.项目实现 路由器AR1配置: 进入系统视图 sys将路由器命名为AR1 sysname AR1关闭信息中心 undo info-center enable 进入g0/0/0接口 int g0/0/0将g0/0/0接口IP地址配置为192.168.10.254/24 ip address 192.168.10.254 24进…...
欢迎 PaliGemma 2 – 来自 Google 的新视觉语言模型
我们很高兴迎来 Google 全新的视觉语言模型 PaliGemma 2,这是 PaliGemma 的一个新版本。与其前代产品一样,PaliGemma 2 使用强大的SigLIP进行视觉处理,但在文本解码部分升级到了最新的 Gemma 2。 https://hf.co/collections/google/siglip-65…...
C++ List(双向链表)
是一个线性链表结构,它的数据由若干个节点构成,每一个节点都包括一个 信息块(即实际存储的数据)、一个前驱指针和一个后驱指针。它无需分配指定 的内存大小且可以任意伸缩,这是因为它存储在非连续的内存空间中&#…...
pip使用方法
1. 安装包: pip install :安装指定的 Python 包。 pip install :安装特定版本的 Python 包。 pip install -r requirements.txt:从文件中读取依赖列表并安装所有列出的包。 pip install --pre :允许安装预发布或开发版…...
websocket再项目中的使用
WebSocket在项目中的使用主要包括以下几个方面: WebSocket的基本概念和原理: 定义:WebSocket是一种基于TCP的协议,实现了浏览器与服务器之间的全双工通信。它通过HTTP/1.1协议的101状态码进行握手,建立连接…...
C语言:指针2(指针变量指向数组)
通过指针引用数组元素 引用一个数组元素,可以用: ① 下标法:如 a[i] 形式。 ② 指针法:如 *(ai) 或者 *(pi) 。其中a是数组名,p是指向数组元素的指针变量,其初值:p a; 案例 需求:…...
心觉:一个人的关注点,决定了他的成长速度
Hi,我是心觉,带你用潜意识化解各种焦虑、内耗,建立无敌自信;教你财富精准显化的实操方法;关注我,伴你一路成长! 每日一省写作265/1000天 在生活和工作中,我们经常会进入一个矛盾:总是…...
【Websokect】服务器https协议下ws连接失败问题及解决办法
在服务器使用HTTPS协议下连接WebSocket时,通常会出现一些常见的问题导致连接失败。以下是一些可能的原因和解决办法: SSL证书配置问题: 确保您的服务器上已正确配置SSL证书,并且证书有效。如果证书配置不正确或者过期,…...
Python 助力 DBA:高效批量管理数据库服务器的多线程解决方案-多库查询汇总工具实现
批量数据库服务器连接测试与数据汇总:Python实现方案 作为数据库服务器运维人员,我们经常需要面对大量服务器的连接测试和数据汇总工作。本文将介绍一个使用Python实现的高效解决方案,可以帮助我们快速完成这些任务。 需求概述 从配置文件…...
如何在繁忙的生活中找到自己的节奏?
目录 一、理解生活节奏的重要性 二、分析当前生活节奏 1. 时间分配 2. 心理状态 3. 身体状况 4. 生活习惯 1. 快慢适中 2. 张弛结合 3. 与目标相符 三、掌握调整生活节奏的策略 1. 设定优先级 2. 合理规划时间 3. 学会拒绝与取舍 4. 保持健康的生活方式 5. 留出…...
uniapp blob格式转换为video .mp4文件使用ffmpeg工具
前言 介绍一下这三种对象使用场景 您前端一旦涉及到文件或图片上传Q到服务器,就势必离不了 Blob/File /base64 三种主流的类型它们之间 互转 也成了常态 Blob - FileBlob -Base64Base64 - BlobFile-Base64Base64 _ File uniapp 上传文件 现在已获取到了blob格式的…...
SQLite建表语句示例(含所有数据类型、索引、自增主键、唯一索引)
下面是一个示例,展示如何创建一个用户信息表。 包含 SQLite 支持的所有数据类型,同时设置主键为自增、一个字段为唯一索引,以及另一个字段为普通索引: -- 创建用户信息表 CREATE TABLE user_info (id INTEGER PRIMARY KEY AUTOI…...
vue常用的一些指令整理
在 Vue.js 中,指令(Directives)是特殊的 HTML 属性,用于在模板中绑定行为。Vue 提供了许多内置指令,你也可以定义自定义指令。以下是指令的分类和常用用法: 1. 内置指令 v-bind 用于动态绑定属性或特性。…...
SSM 搭台,Vue 唱戏:新锐台球厅管理系统的设计与实现盛宴
2相关技术 2.1 MYSQL数据库 MySQL是一个真正的多用户、多线程SQL数据库服务器。 是基于SQL的客户/服务器模式的关系数据库管理系统,它的有点有有功能强大、使用简单、管理方便、安全可靠性高、运行速度快、多线程、跨平台性、完全网络化、稳定性等,非常适…...