面试算法100:三角形中最小路径之和
题目
在一个由数字组成的三角形中,第1行有1个数字,第2行有2个数字,以此类推,第n行有n个数字。例如,下图是一个包含4行数字的三角形。如果每步只能前往下一行中相邻的数字,请计算从三角形顶部到底部的路径经过的数字之和的最小值。从三角形顶部到底部的路径数字之和的最小值为11,对应的路径经过的数字用阴影表示。

说明:从三角形顶部到底部的路径数字之和的最小值为11,对应的路径经过的数字用阴影表示
分析
可以移动三角形每行的位置使它们左端对齐

可以用f(i,j)表示从三角形的顶部出发到达行号和列号分别为i和j(i≥j)的位置时路径数字之和的最小值,同时用T[i][j]表示三角形行号和列号分别为i和j的数字。如果三角形中包含n行数字,那么f(n-1,j)的最小值就是整个问题的最优解。
解
public class Test {public static void main(String[] args) {List<Integer> list1 = Arrays.asList(2);List<Integer> list2 = Arrays.asList(3, 4);List<Integer> list3 = Arrays.asList(6, 5, 7);List<Integer> list4 = Arrays.asList(4, 1, 8, 3);List<List<Integer>> triangle = Arrays.asList(list1, list2, list3, list4);int result = minimumTotal(triangle);System.out.println(result);}public static int minimumTotal(List<List<Integer>> triangle) {int size = triangle.size();int[][] dp = new int[size][size];for (int i = 0; i < size; i++) {for (int j = 0; j <= i; j++) {dp[i][j] = triangle.get(i).get(j);if (i > 0 && j == 0) {// 最左边dp[i][j] += dp[i - 1][j];}else if (i > 0 && i == j) {// 最右边dp[i][j] += dp[i - 1][j - 1];}else if (i > 0) {dp[i][j] += Math.min(dp[i - 1][j], dp[i - 1][j - 1]);}}}int min = Integer.MAX_VALUE;for (int num : dp[size - 1]) {// 答案在最底层,选出一个最小的min = Math.min(min, num);}return min;}
}
相关文章:
面试算法100:三角形中最小路径之和
题目 在一个由数字组成的三角形中,第1行有1个数字,第2行有2个数字,以此类推,第n行有n个数字。例如,下图是一个包含4行数字的三角形。如果每步只能前往下一行中相邻的数字,请计算从三角形顶部到底部的路径经…...
androj studio安装及运行源码
抖音教学视频 目录 1、 jdk安装 2、下载安装androj studio 3 、打开源码安装运行相关组件 4、 安装模拟器 1、 jdk安装 安卓项目也是java开发的,运行在虚拟机上,安装jdk及运行的时候,就会自动生成虚拟机, jdk前面已经讲过&…...
【Web】token机制
🍎个人博客:个人主页 🏆个人专栏:Web ⛳️ 功不唐捐,玉汝于成 目录 前言 正文 机制基本: 优势: 结语 我的其他博客 前言 在当今互联网时代,安全、高效的用户身份验证和资源授…...
JVM 11 调优指南:如何进行JVM调优,JVM调优参数
JVM 11的优化指南:如何进行JVM调优,以及JVM调优参数有哪些”这篇文章将包含JVM 11调优的核心概念、重要性、调优参数,并提供12个实用的代码示例,每个示例都会结合JVM调优参数和Java代码 本文已收录于,我的技术网站 dd…...
横版动作闯关游戏:幽灵之歌 GHOST SONG 中文版
在洛里安荒凉的卫星上,一件长期休眠的死亡服从沉睡中醒来。踏上发现自我、古老谜团和宇宙骇物的氛围2D冒险之旅。探索蜿蜒的洞穴,获得新的能力来揭开这个外星世界埋藏已久的秘密。 游戏特点 发现地下之物 探索这个广阔而美丽如画,充满密室和诡…...
【C++】:C++中的STL序列式容器vector源码剖析
⛅️一 vector概述 vector的使用语法可以参考文章: 总的来说:vector是可变大小数组 特点: 支持快速随机访问。在尾部之外的位置插入或删除元素可能很慢 元素保存在连续的内存空间中,因此通过下标取值非常快 在容器中间位置添加…...
final
//用final修饰的成员变量,必须在声明时或代码块中或构造函数中进行赋值 //但是在声明同时赋值或者代码块中赋值,赋值后不能改变,如果想改变 需要在构造方法中赋值...
【AI】ObjectCenteredSensing
1. 物体检测 .1. 流体 D. V. Q. Rodrigues, D. Rodriguez and C. Li, “Liquid Aerosol Detection Based on Sub-THz Portable Doppler Radars,” 2020 IEEE Asia-Pacific Microwave Conference (APMC), 2020, pp. 504-506, doi: 10.1109/APMC47863.2020.9331483. [pdf] Bala …...
一阶低通滤波器
一阶低通滤波器 X为输入,Y为滤波后得到的输出值;本次的输出结果主要取决于上次的滤波输出值,其中a是和滤波效果有关的一个参数,称为滤波系数;它决定新采样值在本次滤波结果中所占的权重; 滤波系数a越小&a…...
【排序算法】插入排序与希尔排序,你不想知道为什么希尔比插入更快吗?
文章目录 🚀前言🚀插入排序(insertsort)✈️原理✈️代码实现(coding) 🚀总结🚀希尔排序(shellsort)✈️代码实现(coding)✈️为啥希尔…...
Unity中向量的点乘、叉乘区别和作用以及经典案例
文章目录 点乘(Dot Product)叉乘(Cross Product)向量归一化(Normalize)其他作用 unity开发中我们要计算角度,判断位置,常用点乘、叉乘、归一化等等,我们看看他们的使用案…...
(26)Linux 进程通信之共享内存(共享储存空间)
共享内存是System V版本的最后一个进程间通信方式。共享内存,顾名思义就是允许两个不相关的进程访问同一个逻辑内存,共享内存是两个正在运行的进程之间共享和传递数据的一种非常有效的方式。不同进程之间共享的内存通常为同一段物理内存。进程可以将同一…...
体感游戏开发体感互动游戏
体感健身游戏是一种利用特定技术来跟踪和响应玩家身体动作的互动式电子游戏。这种游戏类型的目的是通过有趣、动态的方式鼓励用户进行身体活动和健康锻炼。下面是有关体感健身游戏的一些重要信息: 体感游戏技术背景 体感技术:这些游戏通常使用运动传感…...
vulnhub靶场之DC-5
一.环境搭建 1.靶场描述 DC-5 is another purposely built vulnerable lab with the intent of gaining experience in the world of penetration testing. The plan was for DC-5 to kick it up a notch, so this might not be great for beginners, but should be ok for p…...
为什么选择CRM系统时,在线演示很重要?
想要知道一款CRM管理系统是否满足企业的需求,操作是否简单,运行是否流畅,最直观的方式就是远程演示。否则,光凭厂商的销售人员介绍一下产品,企业就盲目下单,最后发现功能不匹配,还要赔钱赔时间重…...
专业实习day3、4(路由器做内网访问公网)
专业实习 代码 display ip interface brief 显示当前设备下所有接口IP undo IP地址支持覆盖,但是正常的命令不能覆盖必须undo(删除)掉 un in en 在做配置的过程中,设备系统一般都会出现一些提示或者告警之类的东西,从…...
H264码流进行RTP包封装
一.H264基本概念 H.264从框架结构上分为视频编码层(VCL)和网络抽象层(NAL),VCL功能是进行视频编解码,包括运动补偿预测,变换编码和熵编码等功能;NAL用于采用适当的格式对VCL视频数据…...
基于多智能体点对点转换的分布式模型预测控制
matlab2020正常运行 基于多智能体点对点转换的分布式模型预测控制资源-CSDN文库...
性能分析与调优: Linux 实现 缺页剖析与火焰图
目录 一、实验 1.环境 2.缺页(RSS增长)剖析与火焰图 一、实验 1.环境 (1)主机 表1-1 主机 主机架构组件IP备注prometheus 监测 系统 prometheus、node_exporter 192.168.204.18grafana监测GUIgrafana192.168.204.19agent 监测 主机 node_exporter…...
代码随想录算法训练营第17天 | 110.平衡二叉树 + 257. 二叉树的所有路径 + 404.左叶子之和
今日内容 110.平衡二叉树 257. 二叉树的所有路径 404.左叶子之和 110.平衡二叉树 - Easy 题目链接:. - 力扣(LeetCode) 给定一个二叉树,判断它是否是高度平衡的二叉树。 本题中,一棵高度平衡二叉树定义为࿱…...
多云管理“拦路虎”:深入解析网络互联、身份同步与成本可视化的技术复杂度
一、引言:多云环境的技术复杂性本质 企业采用多云策略已从技术选型升维至生存刚需。当业务系统分散部署在多个云平台时,基础设施的技术债呈现指数级积累。网络连接、身份认证、成本管理这三大核心挑战相互嵌套:跨云网络构建数据…...
Appium+python自动化(十六)- ADB命令
简介 Android 调试桥(adb)是多种用途的工具,该工具可以帮助你你管理设备或模拟器 的状态。 adb ( Android Debug Bridge)是一个通用命令行工具,其允许您与模拟器实例或连接的 Android 设备进行通信。它可为各种设备操作提供便利,如安装和调试…...
Docker 运行 Kafka 带 SASL 认证教程
Docker 运行 Kafka 带 SASL 认证教程 Docker 运行 Kafka 带 SASL 认证教程一、说明二、环境准备三、编写 Docker Compose 和 jaas文件docker-compose.yml代码说明:server_jaas.conf 四、启动服务五、验证服务六、连接kafka服务七、总结 Docker 运行 Kafka 带 SASL 认…...
SCAU期末笔记 - 数据分析与数据挖掘题库解析
这门怎么题库答案不全啊日 来简单学一下子来 一、选择题(可多选) 将原始数据进行集成、变换、维度规约、数值规约是在以下哪个步骤的任务?(C) A. 频繁模式挖掘 B.分类和预测 C.数据预处理 D.数据流挖掘 A. 频繁模式挖掘:专注于发现数据中…...
HTML 列表、表格、表单
1 列表标签 作用:布局内容排列整齐的区域 列表分类:无序列表、有序列表、定义列表。 例如: 1.1 无序列表 标签:ul 嵌套 li,ul是无序列表,li是列表条目。 注意事项: ul 标签里面只能包裹 li…...
MODBUS TCP转CANopen 技术赋能高效协同作业
在现代工业自动化领域,MODBUS TCP和CANopen两种通讯协议因其稳定性和高效性被广泛应用于各种设备和系统中。而随着科技的不断进步,这两种通讯协议也正在被逐步融合,形成了一种新型的通讯方式——开疆智能MODBUS TCP转CANopen网关KJ-TCPC-CANP…...
leetcodeSQL解题:3564. 季节性销售分析
leetcodeSQL解题:3564. 季节性销售分析 题目: 表:sales ---------------------- | Column Name | Type | ---------------------- | sale_id | int | | product_id | int | | sale_date | date | | quantity | int | | price | decimal | -…...
如何在最短时间内提升打ctf(web)的水平?
刚刚刷完2遍 bugku 的 web 题,前来答题。 每个人对刷题理解是不同,有的人是看了writeup就等于刷了,有的人是收藏了writeup就等于刷了,有的人是跟着writeup做了一遍就等于刷了,还有的人是独立思考做了一遍就等于刷了。…...
Android 之 kotlin 语言学习笔记三(Kotlin-Java 互操作)
参考官方文档:https://developer.android.google.cn/kotlin/interop?hlzh-cn 一、Java(供 Kotlin 使用) 1、不得使用硬关键字 不要使用 Kotlin 的任何硬关键字作为方法的名称 或字段。允许使用 Kotlin 的软关键字、修饰符关键字和特殊标识…...
深度学习水论文:mamba+图像增强
🧀当前视觉领域对高效长序列建模需求激增,对Mamba图像增强这方向的研究自然也逐渐火热。原因在于其高效长程建模,以及动态计算优势,在图像质量提升和细节恢复方面有难以替代的作用。 🧀因此短时间内,就有不…...
