面试算法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) 给定一个二叉树,判断它是否是高度平衡的二叉树。 本题中,一棵高度平衡二叉树定义为࿱…...
【Linux】C语言执行shell指令
在C语言中执行Shell指令 在C语言中,有几种方法可以执行Shell指令: 1. 使用system()函数 这是最简单的方法,包含在stdlib.h头文件中: #include <stdlib.h>int main() {system("ls -l"); // 执行ls -l命令retu…...
线程与协程
1. 线程与协程 1.1. “函数调用级别”的切换、上下文切换 1. 函数调用级别的切换 “函数调用级别的切换”是指:像函数调用/返回一样轻量地完成任务切换。 举例说明: 当你在程序中写一个函数调用: funcA() 然后 funcA 执行完后返回&…...
渗透实战PortSwigger靶场-XSS Lab 14:大多数标签和属性被阻止
<script>标签被拦截 我们需要把全部可用的 tag 和 event 进行暴力破解 XSS cheat sheet: https://portswigger.net/web-security/cross-site-scripting/cheat-sheet 通过爆破发现body可以用 再把全部 events 放进去爆破 这些 event 全部可用 <body onres…...
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…...
从零实现STL哈希容器:unordered_map/unordered_set封装详解
本篇文章是对C学习的STL哈希容器自主实现部分的学习分享 希望也能为你带来些帮助~ 那咱们废话不多说,直接开始吧! 一、源码结构分析 1. SGISTL30实现剖析 // hash_set核心结构 template <class Value, class HashFcn, ...> class hash_set {ty…...
深度学习习题2
1.如果增加神经网络的宽度,精确度会增加到一个特定阈值后,便开始降低。造成这一现象的可能原因是什么? A、即使增加卷积核的数量,只有少部分的核会被用作预测 B、当卷积核数量增加时,神经网络的预测能力会降低 C、当卷…...
vulnyx Blogger writeup
信息收集 arp-scan nmap 获取userFlag 上web看看 一个默认的页面,gobuster扫一下目录 可以看到扫出的目录中得到了一个有价值的目录/wordpress,说明目标所使用的cms是wordpress,访问http://192.168.43.213/wordpress/然后查看源码能看到 这…...
多模态图像修复系统:基于深度学习的图片修复实现
多模态图像修复系统:基于深度学习的图片修复实现 1. 系统概述 本系统使用多模态大模型(Stable Diffusion Inpainting)实现图像修复功能,结合文本描述和图片输入,对指定区域进行内容修复。系统包含完整的数据处理、模型训练、推理部署流程。 import torch import numpy …...
【Linux系统】Linux环境变量:系统配置的隐形指挥官
。# Linux系列 文章目录 前言一、环境变量的概念二、常见的环境变量三、环境变量特点及其相关指令3.1 环境变量的全局性3.2、环境变量的生命周期 四、环境变量的组织方式五、C语言对环境变量的操作5.1 设置环境变量:setenv5.2 删除环境变量:unsetenv5.3 遍历所有环境…...
tomcat入门
1 tomcat 是什么 apache开发的web服务器可以为java web程序提供运行环境tomcat是一款高效,稳定,易于使用的web服务器tomcathttp服务器Servlet服务器 2 tomcat 目录介绍 -bin #存放tomcat的脚本 -conf #存放tomcat的配置文件 ---catalina.policy #to…...
