当前位置: 首页 > 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;多了一个 / 去…...

【Oracle APEX开发小技巧12】

有如下需求&#xff1a; 有一个问题反馈页面&#xff0c;要实现在apex页面展示能直观看到反馈时间超过7天未处理的数据&#xff0c;方便管理员及时处理反馈。 我的方法&#xff1a;直接将逻辑写在SQL中&#xff0c;这样可以直接在页面展示 完整代码&#xff1a; SELECTSF.FE…...

Java - Mysql数据类型对应

Mysql数据类型java数据类型备注整型INT/INTEGERint / java.lang.Integer–BIGINTlong/java.lang.Long–––浮点型FLOATfloat/java.lang.FloatDOUBLEdouble/java.lang.Double–DECIMAL/NUMERICjava.math.BigDecimal字符串型CHARjava.lang.String固定长度字符串VARCHARjava.lang…...

LLM基础1_语言模型如何处理文本

基于GitHub项目&#xff1a;https://github.com/datawhalechina/llms-from-scratch-cn 工具介绍 tiktoken&#xff1a;OpenAI开发的专业"分词器" torch&#xff1a;Facebook开发的强力计算引擎&#xff0c;相当于超级计算器 理解词嵌入&#xff1a;给词语画"…...

Spring AI与Spring Modulith核心技术解析

Spring AI核心架构解析 Spring AI&#xff08;https://spring.io/projects/spring-ai&#xff09;作为Spring生态中的AI集成框架&#xff0c;其核心设计理念是通过模块化架构降低AI应用的开发复杂度。与Python生态中的LangChain/LlamaIndex等工具类似&#xff0c;但特别为多语…...

CMake控制VS2022项目文件分组

我们可以通过 CMake 控制源文件的组织结构,使它们在 VS 解决方案资源管理器中以“组”(Filter)的形式进行分类展示。 🎯 目标 通过 CMake 脚本将 .cpp、.h 等源文件分组显示在 Visual Studio 2022 的解决方案资源管理器中。 ✅ 支持的方法汇总(共4种) 方法描述是否推荐…...

Mobile ALOHA全身模仿学习

一、题目 Mobile ALOHA&#xff1a;通过低成本全身远程操作学习双手移动操作 传统模仿学习&#xff08;Imitation Learning&#xff09;缺点&#xff1a;聚焦与桌面操作&#xff0c;缺乏通用任务所需的移动性和灵活性 本论文优点&#xff1a;&#xff08;1&#xff09;在ALOHA…...

SiFli 52把Imagie图片,Font字体资源放在指定位置,编译成指定img.bin和font.bin的问题

分区配置 (ptab.json) img 属性介绍&#xff1a; img 属性指定分区存放的 image 名称&#xff0c;指定的 image 名称必须是当前工程生成的 binary 。 如果 binary 有多个文件&#xff0c;则以 proj_name:binary_name 格式指定文件名&#xff0c; proj_name 为工程 名&…...

【7色560页】职场可视化逻辑图高级数据分析PPT模版

7种色调职场工作汇报PPT&#xff0c;橙蓝、黑红、红蓝、蓝橙灰、浅蓝、浅绿、深蓝七种色调模版 【7色560页】职场可视化逻辑图高级数据分析PPT模版&#xff1a;职场可视化逻辑图分析PPT模版https://pan.quark.cn/s/78aeabbd92d1...

MySQL的pymysql操作

本章是MySQL的最后一章&#xff0c;MySQL到此完结&#xff0c;下一站Hadoop&#xff01;&#xff01;&#xff01; 这章很简单&#xff0c;完整代码在最后&#xff0c;详细讲解之前python课程里面也有&#xff0c;感兴趣的可以往前找一下 一、查询操作 我们需要打开pycharm …...

Matlab实现任意伪彩色图像可视化显示

Matlab实现任意伪彩色图像可视化显示 1、灰度原始图像2、RGB彩色原始图像 在科研研究中&#xff0c;如何展示好看的实验结果图像非常重要&#xff01;&#xff01;&#xff01; 1、灰度原始图像 灰度图像每个像素点只有一个数值&#xff0c;代表该点的​​亮度&#xff08;或…...