面试算法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) 给定一个二叉树,判断它是否是高度平衡的二叉树。 本题中,一棵高度平衡二叉树定义为࿱…...
第19节 Node.js Express 框架
Express 是一个为Node.js设计的web开发框架,它基于nodejs平台。 Express 简介 Express是一个简洁而灵活的node.js Web应用框架, 提供了一系列强大特性帮助你创建各种Web应用,和丰富的HTTP工具。 使用Express可以快速地搭建一个完整功能的网站。 Expre…...
React 第五十五节 Router 中 useAsyncError的使用详解
前言 useAsyncError 是 React Router v6.4 引入的一个钩子,用于处理异步操作(如数据加载)中的错误。下面我将详细解释其用途并提供代码示例。 一、useAsyncError 用途 处理异步错误:捕获在 loader 或 action 中发生的异步错误替…...
大话软工笔记—需求分析概述
需求分析,就是要对需求调研收集到的资料信息逐个地进行拆分、研究,从大量的不确定“需求”中确定出哪些需求最终要转换为确定的“功能需求”。 需求分析的作用非常重要,后续设计的依据主要来自于需求分析的成果,包括: 项目的目的…...
突破不可导策略的训练难题:零阶优化与强化学习的深度嵌合
强化学习(Reinforcement Learning, RL)是工业领域智能控制的重要方法。它的基本原理是将最优控制问题建模为马尔可夫决策过程,然后使用强化学习的Actor-Critic机制(中文译作“知行互动”机制),逐步迭代求解…...
【机器视觉】单目测距——运动结构恢复
ps:图是随便找的,为了凑个封面 前言 在前面对光流法进行进一步改进,希望将2D光流推广至3D场景流时,发现2D转3D过程中存在尺度歧义问题,需要补全摄像头拍摄图像中缺失的深度信息,否则解空间不收敛…...
零基础在实践中学习网络安全-皮卡丘靶场(第九期-Unsafe Fileupload模块)(yakit方式)
本期内容并不是很难,相信大家会学的很愉快,当然对于有后端基础的朋友来说,本期内容更加容易了解,当然没有基础的也别担心,本期内容会详细解释有关内容 本期用到的软件:yakit(因为经过之前好多期…...
Unsafe Fileupload篇补充-木马的详细教程与木马分享(中国蚁剑方式)
在之前的皮卡丘靶场第九期Unsafe Fileupload篇中我们学习了木马的原理并且学了一个简单的木马文件 本期内容是为了更好的为大家解释木马(服务器方面的)的原理,连接,以及各种木马及连接工具的分享 文件木马:https://w…...
视频行为标注工具BehaviLabel(源码+使用介绍+Windows.Exe版本)
前言: 最近在做行为检测相关的模型,用的是时空图卷积网络(STGCN),但原有kinetic-400数据集数据质量较低,需要进行细粒度的标注,同时粗略搜了下已有开源工具基本都集中于图像分割这块,…...
使用LangGraph和LangSmith构建多智能体人工智能系统
现在,通过组合几个较小的子智能体来创建一个强大的人工智能智能体正成为一种趋势。但这也带来了一些挑战,比如减少幻觉、管理对话流程、在测试期间留意智能体的工作方式、允许人工介入以及评估其性能。你需要进行大量的反复试验。 在这篇博客〔原作者&a…...
mac 安装homebrew (nvm 及git)
mac 安装nvm 及git 万恶之源 mac 安装这些东西离不开Xcode。及homebrew 一、先说安装git步骤 通用: 方法一:使用 Homebrew 安装 Git(推荐) 步骤如下:打开终端(Terminal.app) 1.安装 Homebrew…...
