当前位置: 首页 > news >正文

Leetcode 三角形最小路径和

在这里插入图片描述

算法思想与代码详解

这段代码采用的是**动态规划(Dynamic Programming)**的思想,用来解决“120. 三角形最小路径和”问题。动态规划通过将问题分解成更小的子问题,并通过保存子问题的解来避免重复计算,从而提高效率。


算法核心思路
  1. 从底向上计算(Bottom-Up Approach)

    • 因为我们要求从顶点到底边的最小路径和,可以从底边开始,逐步向上计算每一层的最优解。
    • 每个位置的最小路径和,取决于当前值和下一层两个可能的相邻路径值中的较小者。
  2. 状态表示(DP数组)

    • 使用一个一维数组 dp 来保存“从当前层到底边的最小路径和”。
    • dp[j] 表示从当前层位置 j 到底边的最小路径和。
  3. 状态转移方程

    • 对于某一层的节点 triangle[i][j],它的最小路径和为:
      [
      dp[j] = \min(dp[j], dp[j + 1]) + triangle[i][j]
      ]
    • dp[j] 表示当前位置 j 往下的最小路径,dp[j+1] 表示下一个位置 j+1 往下的最小路径。
  4. 最终结果

    • 计算完成后,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]] 为例:

  1. 初始化

    • 将最后一层 [4, 1, 8, 3] 赋值到 dp 数组中:
      [
      dp = [4, 1, 8, 3]
      ]
  2. 从倒数第二层开始计算

    • 第 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]
        ]
  3. 最终结果

    • 返回 dp[0],即最小路径和为 11

时间和空间复杂度
  1. 时间复杂度

    • 外层循环从底层到顶层,共 (n-1) 次。
    • 内层循环每层最多运行 (i+1) 次,整体为 (O(n^2))。
    • 总时间复杂度: (O(n^2))。
  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 三角形最小路径和

算法思想与代码详解 这段代码采用的是**动态规划&#xff08;Dynamic Programming&#xff09;**的思想&#xff0c;用来解决“120. 三角形最小路径和”问题。动态规划通过将问题分解成更小的子问题&#xff0c;并通过保存子问题的解来避免重复计算&#xff0c;从而提高效率。…...

DataOps驱动数据集成创新:Apache DolphinScheduler SeaTunnel on Amazon Web Services

引言 在数字化转型的浪潮中&#xff0c;数据已成为企业最宝贵的资产之一。DataOps作为一种文化、流程和实践的集合&#xff0c;旨在提高数据管道的质量和效率&#xff0c;从而加速数据从源头到消费的过程。白鲸开源科技&#xff0c;作为DataOps领域的领先开源原生公司&#xf…...

Android Studio的笔记--BusyBox相关

BusyBox 相关 BusyBoxandroid上安装busybox和使用示例一、下载二、移动三、安装和设置环境变量四、使用 busybox源码下载和查看 BusyBox BUSYBOX BUSYBOX链接https://busybox.net/ 点击链接后如图 点击左边菜单栏的Get BusyBix中的Download Source 跳转到busybox 的下载源码…...

MySQL 存储过程与函数:增强数据库功能

一、MySQL 存储过程与函数概述 &#xff08;一&#xff09;存储过程的定义与特点 存储过程是一组预编译的 SQL 语句集合&#xff0c;它们被存储在数据库中&#xff0c;可根据需要被重复调用。例如&#xff0c;在一个电商系统中&#xff0c;经常需要查询某个时间段内的订单数据…...

网络安全(3)_安全套接字层SSL

4. 安全套接字层 4.1 安全套接字层&#xff08;SSL&#xff09;和传输层安全&#xff08;TLS&#xff09; &#xff08;1&#xff09;SSL/TLS提供的安全服务 ①SSL服务器鉴别&#xff0c;允许用户证实服务器的身份。支持SSL的客户端通过验证来自服务器的证书&#xff0c;来鉴别…...

Git 快速入门

Git 是什么&#xff1f; Git 是一个分布式版本控制系统四大区域&#xff1a; 工作区&#xff1a;项目文件的当前状态&#xff0c;即本地目录。暂存区&#xff1a;保存将要提交的文件快照&#xff0c;是一个中间层&#xff0c;使用git add将文件添加到暂存区。本地仓库&#xf…...

AI学习记录 - 依据 minimind 项目入门

想学习AI&#xff0c;还是需要从头到尾跑一边流程&#xff0c;最近看到这个项目 minimind, 我也记录下学习到的东西&#xff0c;需要结合项目的readme看。 1、github链接 https://github.com/jingyaogong/minimind?tabreadme-ov-file 2、硬件环境&#xff1a;英伟达4070ti …...

数据结构----链表头插中插尾插

一、链表的基本概念 链表是一种线性数据结构&#xff0c;它由一系列节点组成。每个节点包含两个主要部分&#xff1a; 数据域&#xff1a;用于存储数据元素&#xff0c;可以是任何类型的数据&#xff0c;如整数、字符、结构体等。指针域&#xff1a;用于存储下一个节点&#…...

设计模式-读书笔记

确认好&#xff1a; 模式名称 问题&#xff1a;在何时使用模式&#xff0c;包含设计中存在的问题以及问题存在的原因 解决方案&#xff1a;设计模式的组成部分&#xff0c;以及这些组成部分之间的相互关系&#xff0c;各自的职责和协作方式&#xff0c;用uml类图和核心代码描…...

c语言----选择结构

基本概念 选择结构是C语言中用于根据条件判断来执行不同代码块的结构。它允许程序在不同的条件下执行不同的操作&#xff0c;使程序具有决策能力。 if语句 单分支if语句 语法格式&#xff1a; if (条件表达式) { 执行语句块; } 功能&#xff1a; 当条件表达式的值为真&#…...

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&#xff0c;查看缓存 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语音助理&#xff0c;近期上线超拟人方案&#xff0c;不仅大模型语音最快可以1秒内回复&#xff0c;还可以让我们的桌面机器人使用超拟人音色、具备声纹识别等能力&#xff0c;本文以csk6大模型开发板为例实操怎么把超…...

git stash 的文件如何找回

在Git中&#xff0c;如果你使用了git stash命令来保存你的工作进度&#xff0c;但之后想要找回这些被stash的文件&#xff0c;你可以按照以下步骤进行操作&#xff1a; 1. 查看stash列表 首先&#xff0c;使用git stash list命令来查看当前保存的所有stash记录。这个命令会列出…...

皮肤伤口分割数据集labelme格式248张5类别

数据集格式&#xff1a;labelme格式(不包含mask文件&#xff0c;仅仅包含jpg图片和对应的json文件) 图片数量(jpg文件个数)&#xff1a;284 标注数量(json文件个数)&#xff1a;284 标注类别数&#xff1a;5 标注类别名称:["bruises","burns","cu…...

uni-app开发AI康复锻炼小程序,帮助肢体受伤患者康复!

**提要&#xff1a;**近段时间我们收到多个康复机构用户&#xff0c;咨询AI运动识别插件是否可以应用于肢力运动受限患者的康复锻炼中来&#xff0c;插件是可以应用到AI康复锻炼中的&#xff0c;今天小编就为您介绍一下AI运动识别插件在康腹锻炼中的应用场景。 一、康复机构的应…...

双内核架构 Xenomai 4 安装教程

Xenomai 4是一种双内核架构, 继承了Xenomai系列的特点&#xff0c;通过在Linux内核中嵌入一个辅助核心&#xff08;companion core&#xff09;&#xff0c;来提供实时能力。这个辅助核心专门处理那些需要极低且有界响应时间的任务。 本文将在官网教程(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 图数据库&#xff0c;需要将 原 neo4j 数据导入到新的 tugraph 数据库中。预期走csv文件导入导出&#xff0c;但因为格式和数据库设计问题&#xff0c;操作起来比较麻烦&#xff08;可能是个人没…...

启动报错java.lang.NoClassDefFoundError: ch/qos/logback/core/status/WarnStatus

报错信息图片 日志&#xff1a; Exception in thread "Quartz Scheduler [scheduler]" java.lang.NoClassDefFoundError: ch/qos/logback/core/status/WarnStatus先说我自己遇到的问题&#xff0c;我们项目在web设置了自定义的log输出路径&#xff0c;多了一个 / 去…...

音乐标签编辑器:让本地音乐元数据管理效率提升90%的开源工具

音乐标签编辑器&#xff1a;让本地音乐元数据管理效率提升90%的开源工具 【免费下载链接】music-tag-web 音乐标签编辑器&#xff0c;可编辑本地音乐文件的元数据&#xff08;Editable local music file metadata.&#xff09; 项目地址: https://gitcode.com/gh_mirrors/mu/…...

终极B站界面美化指南:如何用BewlyBewly插件快速打造个性化体验

终极B站界面美化指南&#xff1a;如何用BewlyBewly插件快速打造个性化体验 【免费下载链接】BewlyBewly Just make a few small changes to your Bilibili homepage. (English | 简体中文 | 正體中文 | 廣東話) 项目地址: https://gitcode.com/gh_mirrors/be/BewlyBewly …...

2026年,山东专业联想服务器解决方案,涵盖SR858 V3等众多型号!

在当今数字化飞速发展的时代&#xff0c;服务器作为企业数据处理和存储的核心设备&#xff0c;其性能和可靠性至关重要。联想服务器凭借其卓越的性能、丰富的功能和广泛的应用场景&#xff0c;成为众多企业的首选。今天&#xff0c;我们就来详细了解一下联想SR858 V3服务器。联…...

Spring AI vs Python生态:Java开发者如何选择AI工具链?

Spring AI vs Python生态&#xff1a;Java开发者如何构建高效AI工具链&#xff1f; 当Java开发者第一次踏入AI应用开发领域时&#xff0c;往往会面临一个灵魂拷问&#xff1a;是拥抱Python生态的LangChain/LlamaIndex&#xff0c;还是坚持Java技术栈选择Spring AI&#xff1f;这…...

30 分钟搞定答辩 PPT!Paperxie AI 生成器:拯救论文人的「熬夜克星」

paperxie-免费查重复率aigc检测/开题报告/毕业论文/智能排版/文献综述/AIPPThttps://www.paperxie.cn/ppt/createhttps://www.paperxie.cn/ppt/create 一、答辩 PPT 惨案现场&#xff1a;你是不是也在为这四件事崩溃&#xff1f; 论文查重通过的那一刻&#xff0c;你以为终于能…...

别再纠结了!.NET后台任务调度,Hangfire和Quartz.NET到底怎么选?

Hangfire与Quartz.NET深度抉择指南&#xff1a;从业务场景到技术实现的精准匹配 在.NET生态系统中&#xff0c;后台任务调度是几乎所有企业级应用都无法绕开的核心需求。无论是电商平台的订单状态更新、金融系统的日终批处理&#xff0c;还是内容管理系统的定时数据同步&#x…...

35AE92 GJR5137200R0005电子模块

35AE92 GJR5137200R0005 电子模块是一款工业控制系统用的电子控制模块&#xff0c;通常用于西门子或ABB等自动化设备中&#xff0c;承担信号处理、控制逻辑执行及系统接口功能。开头&#xff1a;35AE92 GJR5137200R0005电子模块是工业自动化控制系统的重要组成部分&#xff0c;…...

【ROS2 基础】ROS2与Colcon核心指令速查手册与避坑指南

为了在 ROS2 的日常开发中提升效率&#xff0c;本文为您整理了一份结构化的核心指令速查清单。去除了冗长的理论&#xff0c;直击实战痛点&#xff0c;并附带了多平台差异、性能优化数据以及常见报错的修复方案。 文章目录[TOC]一、 快速入门&#xff1a;3步跑通基础流程二、 版…...

鸿蒙与Android双端蓝牙开发避坑指南:定位权限、虚拟地址与厂商SDK那些事

鸿蒙与Android双端蓝牙开发实战&#xff1a;权限策略与真实地址获取全解析 当你的应用需要同时在鸿蒙和Android设备上稳定运行蓝牙功能时&#xff0c;系统差异就像一片雷区——Android 12的权限拆分、鸿蒙4.0的虚拟地址返回、不同版本间的API兼容性&#xff0c;每个环节都可能让…...

Mojo加速Python科学计算:如何在72小时内将AI推理速度提升8.6倍(附完整可运行代码)

第一章&#xff1a;Mojo与Python混合编程概述Mojo 是一种为 AI 系统量身打造的现代系统编程语言&#xff0c;兼具 Python 的易用性与 C/C 的执行效率。它原生兼容 Python 生态&#xff0c;允许开发者在同一个项目中无缝调用 Python 模块、复用现有 NumPy/Torch 代码&#xff0c…...