【面试经典150 | 动态规划】三角形最小路径和
文章目录
- 写在前面
- Tag
- 题目来源
- 解题思路
- 方法一:动态规划
- 写在最后
写在前面
本专栏专注于分析与讲解【面试经典150】算法,两到三天更新一篇文章,欢迎催更……
专栏内容以分析题目为主,并附带一些对于本题涉及到的数据结构等内容进行回顾与总结,文章结构大致如下,部分内容会有增删:
- Tag:介绍本题牵涉到的知识点、数据结构;
- 题目来源:贴上题目的链接,方便大家查找题目并完成练习;
- 题目解读:复述题目(确保自己真的理解题目意思),并强调一些题目重点信息;
- 解题思路:介绍一些解题思路,每种解题思路包括思路讲解、实现代码以及复杂度分析;
- 知识回忆:针对今天介绍的题目中的重点内容、数据结构进行回顾总结。
Tag
【动态规划】【数组】
题目来源
120. 三角形最小路径和
解题思路
方法一:动态规划
定义状态
f[i][j] 表示从三角形顶部到达位置 (i, j) 的最小路径,i 和 j 分别表示 triangle 数组中的第 i 个数组中的第 j 个元素(索引从 0 开始)。
转移关系
由于每一步只能移动到下一行的「相邻节点」,因此要到达位置 (i, j) 处,上一步只能在位置 (i-1, j) 或 (i-1, j-1)。我们需要在这两个位置中选择一个路径和较小的进行转移,转移关系为:
f [ i ] [ j ] = m i n ( f [ i − 1 ] [ j ] , f [ i − 1 ] [ j − 1 ] ) + t r i a n g l e [ i ] [ j ] f[i][j] = min(f[i-1][j], f[i-1][j-1]) + triangle[i][j] f[i][j]=min(f[i−1][j],f[i−1][j−1])+triangle[i][j]
base case
边界情况有三种,一是初始位置 f[0][0] = triangle[0][0].
二是对于每个数组中的第一个位置,即 f[i][j] 中 j = 0 的情况,上一个位置只能是 (i-1, j),因此此时有:
f [ i ] [ 0 ] = f [ i − 1 ] [ j ] + t r i a n g l e [ i ] [ j ] , i > = 1 f[i][0] = f[i-1][j] + triangle[i][j], i>=1 f[i][0]=f[i−1][j]+triangle[i][j],i>=1
三是 i = j 时,上一个位置只能是 (i-1, j-1),因此有:
f [ i ] [ i ] = f [ i − 1 ] [ i − 1 ] + t r i a n g l e [ i ] [ i ] , i = j f[i][i] = f[i-1][i-1] + triangle[i][i], i=j f[i][i]=f[i−1][i−1]+triangle[i][i],i=j
最后返回
最后返回数组 f[n-1] 中的最小值。
实现代码
class Solution {
public:int minimumTotal(vector<vector<int>>& triangle) {int n = triangle.size();vector<vector<int>> f(n, vector<int>(n));f[0][0] = triangle[0][0];for (int i = 1; i < n; ++i) {f[i][0] = f[i-1][0] + triangle[i][0];for (int j = 1; j < i; ++j) {f[i][j] = min(f[i-1][j], f[i-1][j-1]) + triangle[i][j];}f[i][i] = f[i-1][i-1] + triangle[i][i];}return *min_element(f[n-1].begin(), f[n-1].end());}
};
复杂度分析
时间复杂度: O ( n 2 ) O(n^2) O(n2), n n n 是三角形的行数。
空间复杂度: O ( n 2 ) O(n^2) O(n2)。我们需要一个 n × n n \times n n×n 的二维数组存放所有的状态。
写在最后
如果您发现文章有任何错误或者对文章有任何疑问,欢迎私信博主或者在评论区指出 💬💬💬。
如果大家有更优的时间、空间复杂度的方法,欢迎评论区交流。
最后,感谢您的阅读,如果有所收获的话可以给我点一个 👍 哦。
相关文章:
【面试经典150 | 动态规划】三角形最小路径和
文章目录 写在前面Tag题目来源解题思路方法一:动态规划 写在最后 写在前面 本专栏专注于分析与讲解【面试经典150】算法,两到三天更新一篇文章,欢迎催更…… 专栏内容以分析题目为主,并附带一些对于本题涉及到的数据结构等内容进行…...
【线段树二分】第十三届蓝桥杯省赛C++ A组/研究生组 Python 研究生组《扫描游戏》(C++)
【题目描述】 有一根围绕原点 O 顺时针旋转的棒 OA,初始时指向正上方(Y 轴正向)。 在平面中有若干物件,第 i 个物件的坐标为(,),价值为 。 当棒扫到某个物件时,棒的长度会瞬间增长 ÿ…...
类模板与继承及成员、全局函数的实现
一、类模板与继承 当类模板碰到继承时,需要注意一下几点: 1.当子类继承的父类是一个类模板时,子类在声明的时候,要指定出父类中T的类型 2.如果不指定,编译器无法给子类分配内存 3.如果想灵活指定出父类中T的类型&a…...
怎么制作iOS证书
首先我们登录appuploder官网 搜索 appuploder 第一个就是我们官网啦,网址是:Appuploader home -- A tool improve ios develop efficiency such as submit ipa to appstore and manage ios certificate 可以跨平台开发,无论是Windows还是Ma…...
图床项目实战:从零搭建一个简易图床
项目背景与需求分析 随着互联网的发展,图片分享、存储和管理的需求日益增长。图床作为一种专门用于存储和分享图片的服务,受到了广大用户的欢迎。本项目旨在搭建一个简易的图床系统,满足用户上传、查看和删除图片的基本需求。 技术选型 本项…...
双亲委派机制总结
回顾了一下双亲委派机制,在这记录记录,下一篇会基于打破双亲委派机制来更新 1. 类加载: 多个java文件经过编译打包后生成可运行jar包,最后启动程序。首先需要通过类加载器把主类加载到JVM。主类在运行过程中如果使用到其他类&a…...
C语言数据结构基础————二叉树学习笔记(四)简单的OJ题目练习
1.单值二叉树 965. 单值二叉树 - 力扣(LeetCode) 建立一个新的函数,用函数传参的方法来记录val的值 如上一篇最后的对称二叉树的习题,建立新的函数来传参 多采用使用反对值的方法,因为如果是相等return true的话&am…...
protobuf学习笔记(一):生成一个比较综合的message
一年前学过对应的知识,终究是太潦草了,这几天网上学习了一下,重新写一下笔记。这里是protobuf和golang的结合 一、protobuf protobuf实际上是一种类似json和gob之类的数据格式,也是grpc的御用格式吧(有自己的优势&am…...
[BT]BUUCTF刷题第8天(3.26)
第8天 Web [CISCN2019 华北赛区 Day2 Web1]Hack World 题目明确提示flag在flag表里的flag列,这里先尝试1 返回:你好,glzjin想要一个女朋友。 再尝试1,返回bool(false) 到这里就感觉是布尔盲注的题目类型了(虽然我没…...
【前端】-
相对路径和绝对路径是描述文件位置的两种方式。 1. 相对路径:相对于自己的目标文件的位置,以引用文件之间网页所在位置为参考基础,而建立出的目录路径。因此,当保存于不同目录的网页引用同一个文件时,所使用的路径将不…...
uniapp安装axios
先npm安装 npm i axios然后在项目里面建一个utils文件,再建一个index.js 以下是index.js代码: import axios from axios; const service axios.create({baseURL: //xxxx.xxxxx.com///你的请求接口域名, timeout: 6000, // request timeoutcrossDomai…...
基于javaweb宠物领养平台管理系统设计和实现
基于javaweb宠物领养平台管理系统设计和实现 博主介绍:多年java开发经验,专注Java开发、定制、远程、文档编写指导等,csdn特邀作者、专注于Java技术领域 作者主页 央顺技术团队 Java毕设项目精品实战案例《1000套》 欢迎点赞 收藏 ⭐留言 文末获取源码联…...
网络问题排查方案
PC上不了网初步排查方案步骤 首先查看配置是否正确,是否使用自动获取(DHCP)IP,掩码,网关,如果不是,手动配置确认网关,子网掩码,IP是否配置正确,IP是否已有PC使…...
【CMake】所见所闻所学
Note: 本贴仅记录遇到的CMake的问题,以问题为驱动。 - cmake_minimum_required - project - add_executable - target_include_directories - ExternalProject_Add ExternalProject_Add 是 CMake 中用于管理和构建外部项目的模块。通过 ExternalProject_Add&…...
Linux shell脚本切换为root用户执行命令
首先安装expect。 sudo apt install expect 创建shell脚本文件,示例内容如下: #!/usr/bin/expectspawn su rootexpect {"密码:" {send "00000\r"}"Password:" {send "000000\r"}}send "./…...
儿童护眼灯哪个牌子好?盘点五款满分护眼台灯
为人父母以后,守护孩子的健康成了首要任务。随着孩子慢慢长大,课程的增多,作业也随之增加起来。很多孩子从放学回家就开始伏案在桌子上写作业,哪怕天色逐渐变暗,孩子作业仍旧未写完,作为父母的我们不得不担…...
HangZhou Java Journey P1
Java程序运行时类加载机制 下面是对这个流程的详细说明: JVM启动:当Java程序开始执行时,JVM首先启动。JVM的启动涉及到操作系统级别的进程创建和资源分配。 Bootstrap ClassLoader:JVM启动后,首先会初始化Bootstrap …...
fiddler过滤器使用,隐藏图片、js、css请求
如果抓包过程中不想查看图片、js、css请求,或者只想抓某个ip或者某个网页下的请求,可以在过滤器中设置。 (1)没有开启过滤器 可以看出所有的请求都会抓取,cs、js、图片请求都有 (2)开启过滤器 …...
HTML基础:8个常见表单元素的详解
你好,我是云桃桃。 一个希望帮助更多朋友快速入门 WEB 前端程序媛。 后台回复“前端工具”可免费获取开发工具,持续更新。 今天来说说 HTML 表单。它是用于收集用户输入信息的元素集合。例如文本框、单选按钮、复选框、下拉列表等。 用户经常填写的表…...
密码学之哈希碰撞和生日悖论
哈希碰撞 哈希碰撞是指找到两个不一样的值,它们的哈希值却相同 假设哈希函数的取值空间大小为k ,计算次数为n 先算每个值不一样的概率P’ 所以至少两个值相同(即存在哈希碰撞)的概率P为 生日悖论 假设班里有50个人,求班里至少两个人相同…...
【无标题】260329
一切都只是我想多了么看到你的博文看到你的新年快乐现在看到你删库跑路为什么要这样出现又消失。。。本来就虚无缥缈的一点儿联系又消失殆尽如果现在可以见到你我心里有N个为什么想问你只是觉得憋屈可能是我理解能力不足共情能力有限我猜不到你的心思啊你到底是想联系还是不想联…...
CLIP-GmP-ViT-L-14实操手册:批量图片上传+多提示词并行计算优化
CLIP-GmP-ViT-L-14实操手册:批量图片上传多提示词并行计算优化 1. 项目概述 CLIP-GmP-ViT-L-14是一个经过几何参数化(GmP)微调的CLIP模型,在ImageNet和ObjectNet数据集上达到了约90%的准确率。这个强大的视觉-语言模型能够理解图片内容并将其与文本描述…...
Granite TimeSeries FlowState R1赋能Java应用:商品销量预测微服务开发实录
Granite TimeSeries FlowState R1赋能Java应用:商品销量预测微服务开发实录 最近在做一个电商后台的优化项目,其中一个核心需求就是希望能提前知道商品未来一段时间的销量走势。老板想备货,运营想搞活动,都离不开这个数据。传统的…...
从‘折半查找’到‘二分答案’:LeetCode实战中如何活用这个O(log n)的经典思想
从二分查找到二分答案:LeetCode实战中的O(log n)思想进阶指南 在算法学习与面试准备过程中,二分查找(Binary Search)往往是第一个让初学者感受到算法效率之美的经典案例。这个看似简单的"折半查找"思想,却能…...
突破学术写作瓶颈:WPS-Zotero革新文献管理工作流
突破学术写作瓶颈:WPS-Zotero革新文献管理工作流 【免费下载链接】WPS-Zotero An add-on for WPS Writer to integrate with Zotero. 项目地址: https://gitcode.com/gh_mirrors/wp/WPS-Zotero 在学术写作的征途上,文献管理如同隐形的绊脚石&…...
SenseVoice-Small模型在.NET生态中的集成实践
SenseVoice-Small模型在.NET生态中的集成实践 1. 项目背景与价值 语音识别技术正在快速融入各种应用场景,从智能客服到会议转录,从语音助手到内容创作,处处都能看到它的身影。对于.NET开发者来说,如何在熟悉的生态中集成高质量的…...
实战指南:利用Python可视化常见激活函数(Sigmoid、Tanh、ReLU、PReLU)及其特性对比
1. 为什么需要可视化激活函数? 在深度学习的世界里,激活函数就像是神经网络的"开关",决定了神经元是否应该被激活。但很多初学者在学习时,往往只是死记硬背公式,却不知道这些函数长什么样、在什么情况下会有…...
保姆级教程:用SSC Tool 5.13为先楫HPM6E00EVK生成8轴EtherCAT从站代码(附XML配置避坑点)
先楫HPM6E00EVK实现8轴EtherCAT从站开发实战指南 在工业自动化领域,多轴协同控制的需求日益增长。对于嵌入式开发者而言,如何快速搭建一个稳定可靠的EtherCAT从站系统成为关键挑战。本文将基于先楫HPM6E00EVK开发板,详细解析从代码生成到实际…...
RStudio Server部署与运维实战:从零搭建到高效管理
1. 环境准备:搭建RStudio Server的基石 在开始部署RStudio Server之前,我们需要确保服务器环境已经准备就绪。就像盖房子需要打地基一样,这一步决定了后续所有工作的稳定性。我遇到过不少因为环境问题导致的安装失败案例,大多数都…...
告别玄学调参:在ADS里用Yield Analysis给你的射频滤波器设计上个‘保险’
射频滤波器设计的工程化验证:用ADS Yield Analysis实现稳健性设计 在Wi-Fi 6E和5G毫米波频段快速普及的今天,射频前端模块的性能直接决定了通信质量的上限。作为信号链路上的"守门人",滤波器设计不仅要满足理想仿真环境下的指标要求…...
