当前位置: 首页 > news >正文

DP-力扣 120.三角形最小路径和

给定一个三角形,找出自顶向下的最小路径和。每一步只能移动到下一行中相邻的结点上。

相邻的结点: 下标与上一层结点下标相同或者等于上一层结点下标 + 1 的两个结点。

样例:
例如,给定三角形:
[
[2],
[3,4],
[6,5,7],
[4,1,8,3]
]
自顶向下的最小路径和为 11(即,2 + 3 + 5 + 1 = 11)。

说明:
如果你可以只使用 O(n) 的额外空间(n 为三角形的总行数)来解决这个问题,那么你的算法会很加分。

#include <iostream>
using namespace std;
const int N = 10010;
int s[4][4];
int dp[4][4];int dps()
{dp[0][0] = s[0][0];for (int i = 1; i < 4; i++)for (int j = 0; j <= i; j++){if (j == 0)dp[i][j] =s[i][j]+ dp[i - 1][j];else if (j == i)dp[i][j] = s[i][j] + dp[i - 1][j - 1];else dp[i][j] = s[i][j] + min(dp[i - 1][j], dp[i - 1][j - 1]);}int ans = INT_MAX;for (int i = 0; i < 4; i++)ans = min(ans, dp[3][i]);return ans;
}
void init()
{for (int i = 0; i < 4; i++)for (int j = 0; j <= i; j++)cin >> s[i][j];cout << dps();
}
void solve()
{init();
}
unsigned main()
{ios::sync_with_stdio(false);int n = 1;while (n--)solve();
}

相关文章:

DP-力扣 120.三角形最小路径和

给定一个三角形&#xff0c;找出自顶向下的最小路径和。每一步只能移动到下一行中相邻的结点上。相邻的结点&#xff1a; 下标与上一层结点下标相同或者等于上一层结点下标 1 的两个结点。样例&#xff1a; 例如&#xff0c;给定三角形&#xff1a; [ [2], [3,4], [6,5,7], [4…...

【WEEK3】学习目标及总结【SpringMVC】【中文版】

学习目标&#xff1a; 三周完成SpringMVC入门——第三周 感觉这周很难完成任务了&#xff0c;大概率还会有第四周 学习内容&#xff1a; 参考视频教程【狂神说Java】SpringMVC最新教程IDEA版通俗易懂数据处理JSON交互处理 学习时间及产出&#xff1a; 第三周 MON~FRI 2024.…...

peft模型微调--Prompt Tuning

模型微调&#xff08;Model Fine-Tuning&#xff09;是指在预训练模型的基础上&#xff0c;针对特定任务进行进一步的训练以优化模型性能的过程。预训练模型通常是在大规模数据集上通过无监督或自监督学习方法预先训练好的&#xff0c;具有捕捉语言或数据特征的强大能力。 PEF…...

【算法训练营】周测1

清华大学驭风计划课程链接 学堂在线 - 精品在线课程学习平台 (xuetangx.com) 如果需要答案代码可以私聊博主 有任何疑问或者问题&#xff0c;也欢迎私信博主&#xff0c;大家可以相互讨论交流哟~~ 考题11-1 题目描述 有一个初始时为空的序列&#xff0c;你的任务是维护这个…...

PyTorch Dataset、DataLoader长度

pytorch 可以直接对 Dataset 对象用 len() 求数据集大小&#xff0c;而 DataLoader 对象也可以用 len()&#xff0c;不过求得的是用这个 loader 在一个 epoch 能有几多 iteration&#xff0c;容易混淆。本文记录几种情况的对比。 from torch.utils.data import Dataset, DataL…...

动态IP和静态IP

与静态 IP 地址不同&#xff0c;动态 IP 地址会定期更改。让我们来分析一下&#xff1a; 1. IP 地址基础知识&#xff1a; * IP 地址是一个数字标签&#xff0c;用于唯一标识网络上的每个设备。 * 当设备通过网络通信时&#xff0c;数据会在它们之间来回传输。每个数据包都标有…...

中电金信:技术实践|Flink维度表关联方案解析

导语&#xff1a;Flink是一个对有界和无界数据流进行状态计算的分布式处理引擎和框架&#xff0c;主要用来处理流式数据。它既可以处理有界的批量数据集&#xff0c;也可以处理无界的实时流数据&#xff0c;为批处理和流处理提供了统一编程模型。 维度表可以看作是用户来分析数…...

HQL 55 题【持续更新】

前言 今天开始为期一个多月的 HQL 练习&#xff0c;共 55 道 HQL 题&#xff0c;大概每天两道&#xff0c;从初级函数到中级函数。这次的练习不再是基础的 join 那种通用 SQL 语法了&#xff0c;而是引入了更多 Hive 的函数&#xff08;单行函数、窗口函数等&#xff09;。 我…...

lqb省赛日志[8/37]-[搜索·DFS·BFS]

一只小蒟蒻备考蓝桥杯的日志 文章目录 笔记DFS记忆化搜索 刷题心得小结 笔记 DFS 参考 深度优先搜索(DFS) 总结(算法剪枝优化总结) DFS的模板框架: function dfs(当前状态){if(当前状态 目的状态){}for(寻找新状态){if(状态合法){vis[访问该点]&#xff1b;dfs(新状态);?…...

uni app 钓鱼小游戏

最近姑娘喜欢玩那个餐厅游戏里的钓鱼 &#xff0c;经常让看广告&#xff0c;然后就点点点... 自己写个吧。小鱼的图片自己搞。 有问题自己改&#xff0c;不要私信我 <template><view class"page_main"><view class"top_linear"><v…...

openssl3.2 - note - Decoders and Encoders with OpenSSL

文章目录 openssl3.2 - note - Decoders and Encoders with OpenSSL概述笔记编码器/解码器的调用链OSSL_STORE 编码器/解码器的名称和属性OSSL_FUNC_decoder_freectx_fnOSSL_FUNC_encoder_encode_fn官方文档END openssl3.2 - note - Decoders and Encoders with OpenSSL 概述 …...

分享几个 Selenium 自动化常用操作

最近工作会用到selenium来自动化操作一些重复的工作&#xff0c;那么在用selenium写代码的过程中&#xff0c;又顺手整理了一些常用的操作&#xff0c;分享给大家。 常用元素定位方法 虽然有关selenium定位元素的方法有很多种&#xff0c;但是对于没有深入学习&#xff0c;尤…...

【Python】【数据类型】List (列表) 的常见操作

1. 创建 使用内置函数list()将字符串创建为列表 list1 [a, b, c, d] print(list1 , list1) # list1 [a, b, c, d] list1 list(abcd) print(list1) # [a, b, c, d]使用列表推导式创建列表 list1 [x for x in range(1, 10)] print(list1) # [1, 2, 3, 4, 5, 6, 7, 8, 9]多…...

【C语言】病人信息管理系统

本设计实现了一个病人信息管理系统,通过链表数据结构来存储和操作病人的信息。用户可以通过菜单选择录入病人信息、查找病人信息、修改病人信息、删除病人信息、查看所有病人信息和查看专家信息等操作,还可以根据病人的科室、姓名、性别和联系方式进行查找,以及支持修改病人…...

Java Spring Boot 接收时间格式的参数

报错 JSON parse error: Cannot deserialize value of type java.time.LocalDateTime from String “2024-03-14 12:30:00”: Failed to deserialize java.time.LocalDateTime: (java.time.format.DateTimeParseException) Text ‘2024-03-14 12:30:00’ could not be parsed a…...

【C++】实现红黑树

目录 一、认识红黑树1.1 概念1.2 定义 二、实现红黑树2.1 插入2.2 与AVL树对比 一、认识红黑树 1.1 概念 红黑树是一个二叉搜索树&#xff0c;与AVL树相比&#xff0c;红黑树不再使用平衡因子来控制树的左右子树高度差&#xff0c;而是用颜色来控制平衡&#xff0c;颜色为红色…...

爬虫(六)

复习回顾: 01.浏览器一个网页的加载全过程1. 服务器端渲染html的内容和数据在服务器进行融合.在浏览器端看到的页面源代码中. 有你需要的数据2. 客户端(浏览器)渲染html的内容和数据进行融合是发生在你的浏览器上的.这个过程一般通过脚本来完成(javascript)我们通过浏览器可以…...

最长连续序列 - LeetCode 热题 3

大家好&#xff01;我是曾续缘&#x1f49d; 今天是《LeetCode 热题 100》系列 发车第 3 天 哈希第 3 题 ❤️点赞 &#x1f44d; 收藏 ⭐再看&#xff0c;养成习惯 最长连续序列 给定一个未排序的整数数组 nums &#xff0c;找出数字连续的最长序列&#xff08;不要求序列元素…...

运营模型—RFM 模型

运营模型—RFM 模型 RFM 是什么其实我们前面的文章介绍过,这里我们不再赘述,可以参考运营数据分析模型—用户分层分析,今天我们要做的事情是如何落地RFM 模型 我们的数据如下,现在我们就开始进行数据处理 数据预处理 因为数据预处理没有一个固定的套路,都是根据数据的实…...

YOLOv9|加入2023Gold YOLO中的GD机制!遥遥领先!

专栏介绍&#xff1a;YOLOv9改进系列 | 包含深度学习最新创新&#xff0c;助力高效涨点&#xff01;&#xff01;&#xff01; 一、Gold YOLO摘要 在过去的几年里&#xff0c;YOLO系列模型已经成为实时目标检测领域的领先方法。许多研究通过修改体系结构、增加数据和设计新的损…...

【Java学习笔记】Arrays类

Arrays 类 1. 导入包&#xff1a;import java.util.Arrays 2. 常用方法一览表 方法描述Arrays.toString()返回数组的字符串形式Arrays.sort()排序&#xff08;自然排序和定制排序&#xff09;Arrays.binarySearch()通过二分搜索法进行查找&#xff08;前提&#xff1a;数组是…...

8k长序列建模,蛋白质语言模型Prot42仅利用目标蛋白序列即可生成高亲和力结合剂

蛋白质结合剂&#xff08;如抗体、抑制肽&#xff09;在疾病诊断、成像分析及靶向药物递送等关键场景中发挥着不可替代的作用。传统上&#xff0c;高特异性蛋白质结合剂的开发高度依赖噬菌体展示、定向进化等实验技术&#xff0c;但这类方法普遍面临资源消耗巨大、研发周期冗长…...

线程同步:确保多线程程序的安全与高效!

全文目录&#xff1a; 开篇语前序前言第一部分&#xff1a;线程同步的概念与问题1.1 线程同步的概念1.2 线程同步的问题1.3 线程同步的解决方案 第二部分&#xff1a;synchronized关键字的使用2.1 使用 synchronized修饰方法2.2 使用 synchronized修饰代码块 第三部分&#xff…...

vscode(仍待补充)

写于2025 6.9 主包将加入vscode这个更权威的圈子 vscode的基本使用 侧边栏 vscode还能连接ssh&#xff1f; debug时使用的launch文件 1.task.json {"tasks": [{"type": "cppbuild","label": "C/C: gcc.exe 生成活动文件"…...

AtCoder 第409​场初级竞赛 A~E题解

A Conflict 【题目链接】 原题链接&#xff1a;A - Conflict 【考点】 枚举 【题目大意】 找到是否有两人都想要的物品。 【解析】 遍历两端字符串&#xff0c;只有在同时为 o 时输出 Yes 并结束程序&#xff0c;否则输出 No。 【难度】 GESP三级 【代码参考】 #i…...

Java多线程实现之Callable接口深度解析

Java多线程实现之Callable接口深度解析 一、Callable接口概述1.1 接口定义1.2 与Runnable接口的对比1.3 Future接口与FutureTask类 二、Callable接口的基本使用方法2.1 传统方式实现Callable接口2.2 使用Lambda表达式简化Callable实现2.3 使用FutureTask类执行Callable任务 三、…...

CMake控制VS2022项目文件分组

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

【开发技术】.Net使用FFmpeg视频特定帧上绘制内容

目录 一、目的 二、解决方案 2.1 什么是FFmpeg 2.2 FFmpeg主要功能 2.3 使用Xabe.FFmpeg调用FFmpeg功能 2.4 使用 FFmpeg 的 drawbox 滤镜来绘制 ROI 三、总结 一、目的 当前市场上有很多目标检测智能识别的相关算法&#xff0c;当前调用一个医疗行业的AI识别算法后返回…...

听写流程自动化实践,轻量级教育辅助

随着智能教育工具的发展&#xff0c;越来越多的传统学习方式正在被数字化、自动化所优化。听写作为语文、英语等学科中重要的基础训练形式&#xff0c;也迎来了更高效的解决方案。 这是一款轻量但功能强大的听写辅助工具。它是基于本地词库与可选在线语音引擎构建&#xff0c;…...

虚拟电厂发展三大趋势:市场化、技术主导、车网互联

市场化&#xff1a;从政策驱动到多元盈利 政策全面赋能 2025年4月&#xff0c;国家发改委、能源局发布《关于加快推进虚拟电厂发展的指导意见》&#xff0c;首次明确虚拟电厂为“独立市场主体”&#xff0c;提出硬性目标&#xff1a;2027年全国调节能力≥2000万千瓦&#xff0…...