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

数字三角形(dfs+动态规划）通过率未达100%

news 来源：原创 2025/8/25 21:04:18

数字三角形

题目描述

上图给出了一个数字三角形。从三角形的顶部到底部有很多条不同的路径。对于每条路径，把路径上面的数加起来可以得到一个和，你的任务就是找到最大的和。

路径上的每一步只能从一个数走到下一层和它最近的左边的那个数或者右边的那个数。此外，向左下走的次数与向右下走的次数相差不能超过 1。

输入描述

输入的第一行包含一个整数 N (1≤N≤100)N (1≤N≤100)，表示三角形的行数。

下面的 NN 行给出数字三角形。数字三角形上的数都是 0 至 100 之间的整数。

一、若无红色加粗文字：

代码：

##数字三角形
#斜着走
##动态规划
##状态:dp[i][j]表示从i,j出发可以达到的最大值
##状态转移:左下方或者右下方加起来取值最大 当前状态可以由之前的什么子问题得来,肯定是希望
##从当前位置走到下方值大的一个数字,那么和还要加上当前的,由于需要后面的因此倒起来
##最后一行为边界条件,等于自己,从最后一行开始往下走最大值就是自己
##max(dp[i+1][j],dp[i+1][j+1])+a[i][j]
n=int(input())
a=[]
for i in range(n):a.append(list(map(int,input().split())))
dp=[[0]*(n+1) for _ in range(n+1)]
for i in range(n-1,-1,-1):for j in range(i+1):
##        注意这里是i+1 每行i个数字 上面是n-1 相当于-2故这里是i+1if i==n-1:dp[i][j]=a[n-1][j]else:dp[i][j]=max(dp[i+1][j],dp[i+1][j+1])+a[i][j]print(dp[0][0])

二、有红色加粗文字：

代码：

这里的意思相当于不管前面是怎么走的,前面求出的就是相应位置会得到的最大值,在最后结果那里判断,根据左右步数不超过1,而不超过1的情况有3种,例如左右左偏左,右左右偏右，以及左右左右这种，因此可以发现如果是走奇数步那么一定会偏,走偶数步那么一定会回到正中间。因此后面直接判断即可，同时这里其实没有要求那么严没有在走的过程中保持不超过1

动态规划

##数字三角形
##动态规划
##dp[i][j]表示达到i行j列的时候可以取得的最大值
##状态转移 从左上右上而来,还是两者都可以取最大值
n=int(input())
a=[]
dp=[[0]*(n) for _ in range(n)]
for i in range(n):
##从0开始    a.append(list(map(int,input().split())))
dp[0][0]=a[0][0]
for i in range(1,n):for j in range(i+1):
##       从上方而来if j==0:dp[i][j]=dp[i-1][j]+a[i][j]
##       从左上方来elif j==i:dp[i][j]=dp[i-1][j-1]+a[i][j-1]
##     可以来自左上方也可以来自右下方else:dp[i][j]=max(dp[i-1][j],dp[i-1][j-1])+a[i][j]
##如果是奇数其实走的是偶数步 要达到不超过1 那么回到中线
##dp[n][j//2]
##如果是偶数,其实走的是奇数步 那么即可能偏左也可能偏右
##    就取最大值两边的  
if n%2==0:print(max(dp[n-1][n//2-1],dp[n-1][n//2]))
else:print(dp[n-1][n//2])

深度优先搜索:

代码：

import sys
import os
sys.setrecursionlimit(10000000)
n=int(input())
a=[]
ans=0
for i in range(n):a.append(list(map(int,input().split())))
##深度优先搜索
def dfs(depth,col,tot,left,right):
##    当前所处的行 列 和 左下方次数 右下方次数
##    depth表示第i行if depth==n-1:global ansif abs(left-right)<=1:ans=max(ans,tot)returnif col<len(a[depth+1]):dfs(depth+1,col,tot+a[depth+1][col],left+1,right)if col+1<len(a[depth+1]):dfs(depth+1,col+1,tot+a[depth+1][col+1],left,right+1)
dfs(0,0,a[0][0],0,0)
print(ans)

数字三角形(dfs+动态规划）通过率未达100%

数字三角形题目描述上图给出了一个数字三角形。从三角形的顶部到底部有很多条不同的路径。对于每条路径，把路径上面的数加起来可以得到一个和，你的任务就是找到最大的和。路径上的每一步只能从一个数走到下一层和它最近的左边的那个数或者右边的那…...

编程日记 2025/8/25 21:04:18

版本控制工具——Git

目录【版本控制系统】【Git概述】【Git下载】【Git初始化本地仓库并推送】【克隆目标仓库】【Git团队开发的一种流程】【Git客户端TortoiseGit】【下载、克隆和分支之间的区别】【下载GitHub中的子文件夹】【不用魔法的访问方法】【GitHub官方文档】【版…...

编程日记 2025/8/20 13:10:49

计算机网络学习前言

前言该部分说明计算机网络是什么？它有什么作用和功能？值不值得我们去学习？我们该如何学习？这几个部分去大概介绍计算机网络这门课程，往后会介绍计算机网络的具体知识点。 1.计算机网络是什么？ 计算机网…...

编程日记 2025/8/25 19:31:21

Python爬虫第6节-requests库的基本用法

目录前言一、准备工作二、实例引入三、GET请求 3.1 基本示例 3.2 抓取网页 3.3 抓取二进制数据 3.4 添加headers 四、POST请求五、响应前言前面我们学习了urllib的基础使用方法。不过，urllib在实际应用中存在一些不便之处。以网页验证和Cookies处理…...

编程日记 2025/8/25 20:57:36

当实体类中的属性名和表中的字段名不一样，怎么办

在不同的持久化框架中，当实体类中的属性名和表中的字段名不一致时，有不同的解决办法，下面为你详细介绍： 1. MyBatis MyBatis 是一个流行的持久层框架，有两种主要方式来处理属性名和字段名不一致的情况。方式一&…...

编程日记 2025/8/25 20:59:07

我用deepseek制作了一份建设项目从立项到验收全流程手册《从蓝图到交付：建设项目全生命周期管理实战手册》

建设项目全流程详解（2025年更新版） ‌一、立项决策阶段‌ ‌项目建议书编制‌ 明确建设背景、必要性、初步规模及投资估算，形成《项目建议书》报审材料 ‌12 ‌可行性研究深化‌ 完成市场供需分析、技术方案比选、环境影响评估、财务敏感性…...

编程日记 2025/8/25 20:56:12

力扣HOT100之链表：19. 删除链表的倒数第 N 个结点

这道题的思路比较简单，直接定义一个虚拟头节点，然后再定义快慢指针，快慢指针在初始状态下都指向虚拟头节点，然后让快指针先走n步，慢指针停在原地，然后快慢指针同步前进，当快指针fast指向最后一个…...

编程日记 2025/8/25 21:01:11

【Django】教程-11-ajax弹窗实现增删改查

【Django】教程-1-安装创建项目目录结构介绍【Django】教程-2-前端-目录结构介绍【Django】教程-3-数据库相关介绍【Django】教程-4-一个增删改查的Demo 【Django】教程-5-ModelForm增删改查规则校验【正则钩子函数】【Django】教程-6-搜索框-条件查询前后端【Django】教程…...

编程日记 2025/8/25 20:58:13

大厂算法面试 7 天冲刺：第7天-系统设计与模拟面试实战 —— 架构思维 + Java落地

🏗️ 第7天：系统设计与模拟面试实战 —— 架构思维 Java落地 📚 一、What：系统设计是什么？ 系统设计是对一个复杂系统的高可用、高性能、高扩展性架构进行顶层思考和具体实现的过程。 🔧 涉及核心主题&a…...

编程日记 2025/8/25 21:04:18

面试题汇总06-场景题线上问题排查难点亮点

面试题汇总06-场景题&线上问题排查&难点亮点【一】场景题【1】订单到期关闭如何实现【2】每天100w次登录请求，4C8G机器如何做JVM调优？（1）问题描述和分析（2）堆内存设置（3）垃圾收集器选择（4）各区大小设置（5）添加必要的日志【3】如果你的业务量突然提升100倍…...

编程日记 2025/8/25 20:58:14

AI训练存储架构革命：存储选型白皮书与万卡集群实战解析

一、引言在人工智能技术持续高速发展的当下，AI 训练任务对存储系统的依赖愈发关键，而存储系统的选型也变得更为复杂。不同的 AI 训练场景，如机器学习与大模型训练，在模型特性、GPU 使用数量以及数据量带宽等方面的差异&#xff…...

编程日记 2025/8/22 11:36:41

数据结构实验3.1：顺序栈的基本操作与进制转换

文章目录一，问题描述二，基本要求三，算法分析四，示例代码五，实验操作六，运行效果一，问题描述在数据处理中，常常会遇到需要对链接存储的线性表进行操作的情况。本次任务聚焦于将链…...

编程日记 2025/8/25 21:03:40

https://hub.docker.com/r/dorowu/ubuntu-desktop-lxde-vnc 下载nvc 客户端 https://downloads.realvnc.com/download/file/viewer.files/VNC-Viewer-7.12.0-Windows.exe 服务端 docker pull dorowu/ubuntu-desktop-lxde-vnc#下载成功 docker pull dorowu/ubuntu-desktop-l…...

编程日记 2025/8/19 19:24:46

JGraphT 在 Spring Boot 中的应用实践

1. 引言 1.1 什么是 JGraphT JGraphT 是一个用于处理图数据结构和算法的 Java 库，提供了丰富的图类型和算法实现。 1.2 为什么使用 JGraphT 丰富的图类型：支持简单图、多重图、伪图等多种图类型。强大的算法库：提供最短路径、最小生成树、拓扑排序等多种算法。易于集成：…...

编程日记 2025/8/25 21:01:12

.net6 中实现邮件发送

一、开启邮箱服务先要开启邮箱的 SMTP 服务，获取授权码，在实现代码发送邮件中充当邮箱密码用。在邮箱的设置 > 账号 > POP3/IMAP/SMTP/Exchange/CardDAV/CalDAV服务中，把 SMTP 服务开启，获取授权码。二、安装库安装 …...

编程日记 2025/8/20 12:45:20

MySQL 触发器与存储过程：数据库的自动化工厂

在数据世界的工业区，有一座运转高效的自动化工厂，那里的机器人日夜不停地处理数据…这就是 MySQL 的触发器与存储过程系统，它让数据库从"手工作坊"变成了"现代化工厂"… 什么是 MySQL 触发器与存储过程？&…...

编程日记 2025/8/25 21:01:10

计科数据库第二次上机操作--实验二表的简单查询

一、建数据库和表 1．启动数据库服务软件 Navicat 2．在 Navicat 中建立数据库 test 3. 在test数据库上建立teacher表： 二、基本查询 2.1 从teacher表中分别检索出教师的所有信息 SELECT * FROM teacher WHERE 教工号2000; SELECT * FROM t…...

编程日记 2025/8/24 2:16:00

⭐算法OJ⭐滑动窗口最大值【双端队列(deque)】Sliding Window Maximum

文章目录双端队列(deque)详解基本特性常用操作1. 构造和初始化2. 元素访问3. 修改操作4. 容量操作性能特点时间复杂度：空间复杂度： 滑动窗口最大值题目描述方法思路解决代码双端队列(deque)详解双端队列(deque，全称double-ended queue)是…...

编程日记 2025/8/25 21:03:40

LeetCode刷题SQL笔记

系列博客目录文章目录系列博客目录1.distinct关键字去除重复2.char_length()3.group by 与 count()连用4.date类型有个函数datediff()5.mod 函数6.join和left join的区别1. **JOIN（内连接，INNER JOIN）**示例： 2. **LEFT JOIN&a…...

编程日记 2025/8/25 20:59:52

Ubuntu中MATLAB启动图标设置

打开终端，键入 su root 输入root密码键入：vi /usr/share/applications/Matlab.desktop 打开了一个空白文档，按键“i”，进入编辑模式，键入如下内容： [Desktop Entry] NameMatlabR2017b CommentMatlab R…...

编程日记 2025/8/25 20:58:13

Django分页教程及示例

推荐超级课程：本地离线DeepSeek AI方案部署实战教程【完全版】Docker快速入门到精通Kubernetes入门到大师通关课AWS云服务快速入门实战目录完整代码示例：结论Django的分页模块允许你将大量数据分割成更小的块（页面）。这对于以可管理的方式显示项目列表，如博客文章或产品…...

编程日记 2025/8/25 21:02:17

Ansible的使用

##### Ansible使用环境 - 控制节点 - 安装Ansible软件 - Python环境支持：Python>2.6 - 必要的模块：如PyYAML等 - 被控节点 - 启用SSH服务 - 允许控制节点登录，通常设置免密登录 - Python环境支持 http://www.ansible.com/ …...

编程日记 2025/8/22 13:37:19

JBDC Java数据库连接（1）

目录 JDBC概述定义 JDBC API 实例 JDBC搭建建立与数据库连接： 形式： 实例获得Satement执行sql语句 Satement中的方法: 实例实例 JDBC概述定义 JDBC（Java DataBase Connectivity）java数据库连接是一种用于执行SQL…...

编程日记 2025/8/25 21:03:41

tomcat的负载均衡和会话保持

写你的想写的东西，写在tomcat的默认发布目录中这里写了一个jsp的文件访问成功可以用nginx实现反向代理 tomcat负载均衡实现： 这里使用的算法是根据cookie值进行哈希，根据ip地址哈希会有问题.如果是同一台主机再怎么访问都是同一个ip。 t…...

编程日记 2025/8/25 15:32:55

蓝桥杯 web 新鲜的蔬菜（css3）

思路： 首先将.box容器设置为网格布局 display:grid;同时将网格分成3列3行然后：通过子选择器或后代选择器选中相应的元素，再通过 grid-area 将其调整到相应的位置答案： .box {display: grid;grid-template-columns: 1fr 1fr …...

编程日记 2025/8/20 2:26:42

【AI学习】初步了解TRL

TRL（Transformer Reinforcement Learning） 是由 Hugging Face 开发的一套基于强化学习（Reinforcement Learning, RL）的训练工具，专门用于优化和微调大规模语言模型（如 GPT、LLaMA 等）。它结合了…...

编程日记 2025/8/25 20:57:35

2025-04-07 NO.3 Quest3 MR 配置

文章目录 1 MR 介绍1.1 透视1.2 场景理解1.3 空间设置 2 配置 MR 环境2.1 场景配置2.2 MR 配置 3 运行测试配置环境： Windows 11Unity 6000.0.42f1Meta SDK v74.0.2Quest3 1 MR 介绍 1.1 透视透视（Passthrough）是将应用的背景从虚拟的…...

编程日记 2025/8/25 20:58:12

Kafka在Vue和Spring Boot中的使用实例

Kafka在Vue和Spring Boot中的使用实例一、项目概述本项目演示了如何在Vue前端和Spring Boot后端中集成Kafka，实现实时消息的发送和接收，以及数据的实时展示。后端实现：springboot配置、kafka配置、消息模型和仓库、消息服务和消费者、we…...

编程日记 2025/8/25 20:56:13

层归一化详解及在 Stable Diffusion 中的应用分析

在深度学习中，归一化（Normalization）技术被广泛用于提升模型训练的稳定性和收敛速度。本文将详细介绍几种常见的归一化方式，并重点分析它们在 Stable Diffusion 模型中的实际使用场景。一、常见的归一化技术名称归一化维度应用…...

编程日记 2025/8/20 7:56:18

【C++DFS 马拉车】3327. 判断 DFS 字符串是否是回文串|2454

本文涉及知识点 CDFS 马拉车 LeetCode3327. 判断 DFS 字符串是否是回文串给你一棵 n 个节点的树，树的根节点为 0 ，n 个节点的编号为 0 到 n - 1 。这棵树用一个长度为 n 的数组 parent 表示，其中 parent[i] 是节点 i 的父节点。由于节点 …...

编程日记 2025/8/25 20:58:14

前端开发vue项目（node-modules 可视化神器 Node Modules Inspector）

node-modules 可视化神器 Node Modules Inspector 简介功能特点使用场景实现原理使用Node Modules Inspector提供简介 Node Modules Inspector 是一个用于检查和分析 Node.js 项目中模块依赖关系的工具功能特点依赖分析：它能够深入剖析 Node.js项目中的模块依…...

编程日记 2025/8/25 20:59:51

25统计建模半自动化辅助排版模板及论文排版格式要求

1.除封面页外，不得在其他页出现学校、参赛队及指导教师的信息。 2.目录应由论文的篇、章、节、条、款以及附录题录等的序号、题名和页码组成。正文页码单独编列，其页码从正文第一页开始编写。 3.标题和正文：论文正文总标题（题目…...

编程日记 2025/8/24 8:33:31

武汉迅狐科技：AI赋能企业营销，打造智能获客新范式

在数字化营销竞争日益激烈的今天，武汉迅狐科技有限公司凭借其创新的AI技术和智能营销解决方案，正在帮助企业突破传统获客瓶颈，实现营销效率的指数级提升。作为一家专注于AI获客软件研发的高新技术企业，迅狐科技推出的矩阵系统、数…...

编程日记 2025/8/20 2:36:04

Tomcat：Java Web 应用开发的核心容器

在Java Web开发领域，Apache Tomcat凭借其开源特性、轻量级架构和强大的功能支持，成为开发者部署和运行Servlet、JSP应用的首选容器。作为Apache软件基金会旗下的Jakarta项目成果，Tomcat不仅实现了Java EE（现Jakarta EE&#xff09…...

编程日记 2025/8/25 13:26:22

Tomcat 安装与配置：超详细指南

目录一、安装前的准备工作（一）配置 JAVA_HOME 环境变量二、下载 Tomcat（一）Windows 系统（二）macOS/Linux 系统三、安装 Tomcat（一）Windows 系统（二）Linux …...

编程日记 2025/8/25 2:17:14

科技快讯 | DeepSeek 公布模型新学习方式；Meta发布开源大模型Llama 4；谷歌推出 Android Auto 14.0 正式版

Meta发布开源大模型Llama 4，首次采用“混合专家架构“ 4月6日，Meta推出开源AI模型Llama 4，包括Scout和Maverick两个版本，具备多模态处理能力。Scout和Maverick参数量分别为170亿和4000亿，采用混合专家架构。Meta同时训…...

编程日记 2025/8/25 21:01:10

skynet.netpack四个核心函数详解

目录 1. netpack.filter(queue, msg, sz)2. netpack.pop(queue)3. netpack.tostring(msg, sz)4. netpack.clear(queue)完整使用场景示例总结在 Skynet 中，netpack 模块提供了四个核心函数，用于处理网络数据包的接收、粘包解析和队列管理。以下是这四个函…...

编程日记 2025/8/25 5:55:55

Zephyr与Linux核心区别及适用领域分析

一、核心定位与目标场景特性Zephyr RTOSLinux目标领域物联网终端、实时控制系统（资源受限设备）服务器、桌面系统、复杂嵌入式设备（如路由器）典型硬件MCU（ARM Cortex-M, RISC-V），内存<1MBMP…...

编程日记 2025/8/25 20:56:08

Linux网络编程（十五）——优于select的epoll

文章目录 15 优于select的epoll 15.1 epoll理解及应用 15.1.1 基于select的I/O复用技术速度慢的原因 15.1.2 select的优点 15.1.3 实现epoll时必要的函数和结构体 15.1.4 epoll_creat1 15.1.5 epoll_ctl 15.1.6 epoll_wait 15.1.7 基于epoll的回声服务器端 15.2 条件…...

编程日记 2025/8/25 6:51:45

PhotoShop学习07

1.为图像添加纹理图层混合模式是混合 2 张图片的一种快捷方式，一般情况下为图片添加纹理外观可以用到混合模式。这里有一副图片，我可以为其添加纹理，使之呈现出不同的效果。首先需要为当前图层添加一个纹理图片，可以使用置入嵌…...

编程日记 2025/8/25 20:58:13

【缓存击穿】Java的“SingleFlight”解决方案

在Java中实现类似Golang的SingleFlight机制，可以通过以下步骤解决缓存击穿问题。该方案使用ConcurrentHashMap管理并发请求，并通过CompletableFuture实现异步结果合并。实现代码 import java.util.concurrent.Callable; import java.util.concurrent.…...

编程日记 2025/8/25 19:23:27

createContext+useContext+useReducer组合管理React复杂状态

createContext、useContext 和 useReducer 的组合是 React 中管理全局状态的一种常见模式。这种模式非常适合在不引入第三方状态管理库（如 Redux）的情况下，管理复杂的全局状态。以下是一个经典的例子，展示如何使用 createContex…...

编程日记 2025/8/25 20:59:07

海外直播平台交互设计师简历模板

营销团队管理技巧培训PPT啊，其实是一个非常有用的工具呢！它不仅能帮助管理者梳理思路，还能让团队成员快速掌握关键技能。说实话，一个好的PPT就像一位优秀的导师，在会议室里就能让人眼前一亮！比如有一次我参…...

编程日记 2025/8/25 20:57:35

基于springboot微信小程序课堂签到及提问系统(源码+lw+部署文档+讲解)，源码可白嫖!

摘要随着信息时代的来临，过去的课堂签到及提问管理方式的缺点逐渐暴露，本次对过去的课堂签到及提问管理方式的缺点进行分析，采取计算机方式构建基于微信小程序的课堂签到及提问系统。本文通过阅读相关文献，研究国内外相关技术&a…...

编程日记 2025/8/25 21:03:41

MCU软件开发使用指针有哪些坑？

目录 1、空指针访问 2、野指针（未初始化的指针） 3、指针越界 4、内存泄漏 5、悬空指针 6、指针类型不匹配 7、多任务环境中的指针访问 8、对齐问题在MCU软件开发中，使用指针虽然可以提高程序的灵活性和性能，但也存在许多…...

编程日记 2025/8/20 19:44:35

ubuntu 20.04 编译和运行SC-LeGo-LOAM

1.搭建文件目录和clone代码 mkdir -p SC-LeGo-LOAM/src cd SC-LeGo-LOAM/src git clone https://github.com/AbangLZU/SC-LeGO-LOAM.git cd .. 2.修改代码需要注意的是原作者使用的是Ouster OS-64雷达，需要更改utility.h文件中适配自己的雷达类型，而…...

编程日记 2025/8/22 17:19:52

FPGA_DDR(一) 仿真

对ddr进行读写实验，用了vivado的ddr的模型进行仿真 1 创建AXI_mig的ip核选择axi 选择自己的型号，这里是ddr的位宽32，但是axi的话是256位宽选择nobuffer，没有缓冲器选择自己匹配引脚默认后面默认即可生成ip，时间…...

编程日记 2025/8/22 12:34:55

【Spec2MP：项目管理之项目人力管理】

芯片设计项目中如何打造战斗力强悍的团队？ 引言：芯片设计项目的核心是人芯片设计是一项高度复杂、跨学科协作的工程，团队的专业性、协作效率和凝聚力直接影响项目成败。本文结合某芯片项目人力管理文档，从目标、职责、价值观、架…...

编程日记 2025/8/23 10:49:01

windows10下PointNet官方代码Pytorch实现

PointNet模型运行 1.下载源码并安装环境 GitCode - 全球开发者的开源社区,开源代码托管平台GitCode是面向全球开发者的开源社区,包括原创博客,开源代码托管,代码协作,项目管理等。与开发者社区互动,提升您的研发效率和质量。https://gitcode.com/gh_mirrors/po/pointnet.pyto…...

编程日记 2025/8/21 2:41:31

阿里云大模型训练与推理开发

本文主要描述阿里云大模型开发环境的搭建、训练数据集的制作流程、大模型如何训练数据集以及如何利用已训练完成的模型执行推理。开发环境搭建 ModelScope社区是阿里云通义千问开源的大模型开发者社区。如上所示，安装ModelScope社区大模型基础库开发框架的命令行…...

编程日记 2025/8/21 12:15:45

数字三角形

题目描述

输入描述

一、若无红色加粗文字：

代码：

二、有红色加粗文字 ：

代码：

动态规划

深度优先搜索:

代码：

相关文章：

二、有红色加粗文字：