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

python-leetcode-解决智力问题

2140. 解决智力问题 - 力扣(LeetCode)

这道题是一个典型的 动态规划(Dynamic Programming, DP) 问题,可以使用 自底向上 的方式解决。

思路

  1. 定义状态
    dp[i] 表示从第 i 题开始,能获得的最高分数。

  2. 状态转移方程

    • 选择解决第 i
      • 这样可以获得 questions[i][0] 分,并且需要跳过 questions[i][1] 题。
      • 下一次可以从 i + questions[i][1] + 1 题开始,即 dp[i] = questions[i][0] + dp[i + questions[i][1] + 1]
    • 选择跳过第 i
      • 这样可以从 i+1 题开始,即 dp[i] = dp[i+1]
    • 取两者的最大值: dp[i]=max⁡(questions[i][0]+dp[i+questions[i][1]+1],dp[i+1])
  3. 边界条件

    • dp[n] = 0 (当超过最后一题时,得分为 0)。
  4. 计算顺序

    • 我们需要从 后往前 计算 dp[i],因为 dp[i] 依赖于 dp[i+1]dp[i + questions[i][1] + 1]

代码实现

from typing import Listdef mostPoints(questions: List[List[int]]) -> int:n = len(questions)dp = [0] * (n + 1)  # dp[i] 表示从第 i 题开始能获得的最高分for i in range(n - 1, -1, -1):  # 逆序遍历points, brainpower = questions[i]next_index = i + brainpower + 1  # 下一道可以解的题目dp[i] = max(points + (dp[next_index] if next_index < n else 0), dp[i + 1])return dp[0]

复杂度分析

  • 时间复杂度:O(n),我们只需遍历 questions 一次,每次 O(1) 计算 dp[i]
  • 空间复杂度:O(n),用于存储 dp 数组。

示例

输入
questions = [[3, 2], [4, 3], [4, 4], [2, 5]]
print(mostPoints(questions))
输出
5

优化(O(1) 空间)

我们可以只用一个变量来存储 dp[i+1],这样 dp 数组就不需要额外存储所有状态:

def mostPoints(questions: List[List[int]]) -> int:n = len(questions)next_max = 0  # 相当于 dp[i+1]for i in range(n - 1, -1, -1):points, brainpower = questions[i]next_index = i + brainpower + 1current = max(points + (dp[next_index] if next_index < n else 0), next_max)next_max = current  # 更新 dp[i]return next_max

这样,我们将 空间复杂度优化为 O(1)

相关文章:

python-leetcode-解决智力问题

2140. 解决智力问题 - 力扣&#xff08;LeetCode&#xff09; 这道题是一个典型的 动态规划&#xff08;Dynamic Programming, DP&#xff09; 问题&#xff0c;可以使用 自底向上 的方式解决。 思路 定义状态&#xff1a; 设 dp[i] 表示从第 i 题开始&#xff0c;能获得的最高…...

引领变革!北京爱悦诗科技有限公司荣获“GAS消费电子科创奖-产品创新奖”!

在2025年“GAS消费电子科创奖”评选中&#xff0c;北京爱悦诗科技有限公司提交的“aigo爱国者GS06”&#xff0c;在技术创新性、设计创新性、工艺创新性、智能化创新性及原创性五大维度均获得评委的高度认可&#xff0c;荣获“产品创新奖”。 这一奖项不仅是对爱悦诗在消费电子…...

微信小程序+SpringBoot的单词学习小程序平台(程序+论文+讲解+安装+修改+售后)

感兴趣的可以先收藏起来&#xff0c;还有大家在毕设选题&#xff0c;项目以及论文编写等相关问题都可以给我留言咨询&#xff0c;我会一一回复&#xff0c;希望帮助更多的人。 系统背景 &#xff08;一&#xff09;社会需求背景 在全球化的大背景下&#xff0c;英语作为国际…...

wordpress分类名称调用的几种情况

在WordPress中&#xff0c;如果你想调用当前分类的名称&#xff0c;可以使用single_cat_title()函数。以下是一些常见的使用方法和场景&#xff1a; 1. 在分类页面调用当前分类名称 如果你正在分类存档页面(category.php)中&#xff0c;可以直接使用single_cat_title()函数来…...

HMC7043和HMC7044芯片配置使用

一,HMC7043芯片 MC7043独特的特性是对14个通道分别进行独立灵活的相位管理。所有14个通道均支持频率和相位调整。这些输出还可针对50 Ω或100 Ω内部和外部端接选项进行编程。HMC7043器件具有RF SYNC功能,支持确定性同步多个HMC7043器件,即确保所有时钟输出从同一时钟沿开始…...

html播放本地音乐

本地有多个音乐文件&#xff0c;想用 html 逐个播放&#xff0c;或循环播放&#xff0c;并设置初始音量。 audio 在 html 中播放音乐文件用 audio 标签&#xff1a; controls 启用控制按钮&#xff0c;如进度条、播放、音量、速度等。不加不显示任何 widget。autoplay 理应启…...

Windows11下玩转 Docker

一、前提准备 WSL2&#xff1a;Windows 提供的一种轻量级 Linux 运行环境&#xff0c;具备完整的 Linux 内核&#xff0c;并支持更好的文件系统性能和兼容性。它允许用户在 Windows 系统中运行 Linux 命令行工具和应用程序&#xff0c;而无需安装虚拟机或双系统。Ubuntu 1.1 安…...

vLLM + Open-WebUI 本地私有化部署 DeepSeek-R1-Distill-Qwen-32B 方案

一、vLLM 部署 DeepSeek-R1-Distill-Qwen-32B DeepSeek-R1-Distill 系列模型是 DeepSeek-R1 的蒸馏模型&#xff0c;官方提供了从 1.5B - 70B 不同尺寸大小的模型。特别适合在计算资源有限的环境中部署。 DeepSeek-R1 各个版本的蒸馏模型评估结果如下&#xff1a; 其中 DeepS…...

【基础知识】回头看Maven基础

背景 项目过程中&#xff0c;对于Maven的pom.xml文件&#xff0c;很多时候&#xff0c;我通过各种参考、仿写&#xff0c;最终做出想要的效果。 但实际心里有些迷糊&#xff0c;不清楚具体哪个基础的配置所实现的效果。 今天&#xff0c;特意回过头来&#xff0c;了解Maven的基…...

在 MyBatis 中,若数据库字段名与 SQL 保留字冲突解决办法

在 MyBatis 中&#xff0c;若数据库字段名与 SQL 保留字冲突&#xff0c;可通过以下方法解决&#xff1a; 目录 一、使用转义符号包裹字段名二、通过别名映射三、借助 MyBatis-Plus 注解四、全局配置策略&#xff08;辅助方案&#xff09;最佳实践与注意事项 一、使用转义符号…...

docker-compose Install reranker(fastgpt支持) GPU模式

前言BGE-重新排名器 与 embedding 模型不同,reranker 或 cross-encoder 使用 question 和 document 作为输入,直接输出相似性而不是 embedding。 为了平衡准确性和时间成本,cross-encoder 被广泛用于对其他简单模型检索到的前 k 个文档进行重新排序。 例如,使用 bge 嵌入模…...

200W数据需要去重,如何优化?

优化去重逻辑的时间取决于多个因素&#xff0c;包括数据量、数据结构、硬件性能&#xff08;CPU、内存&#xff09;、去重算法的实现方式等。以下是对优化去重逻辑的详细分析和预期优化效果&#xff1a; 1. 去重逻辑的性能瓶颈 时间复杂度&#xff1a;使用HashSet去重的时间复…...

使用免费IP数据库离线查询IP归属地

一、准备工作 1.下载免费IP数据库 首先&#xff0c;访问 MaxMind官网&#xff08;https://www.maxmind.com/en/home&#xff09;如果你还没有MaxMind账号&#xff0c;可以通过此链接地址&#xff08;https://www.maxmind.com/en/geolite2/signup&#xff09;进行账号注册&…...

【游戏】【客户端性能测试】

待续… 一、 常见指标 1. 越高越好 FPS 2. 越低越好 网络流量CPU内存&#xff08;PSS&#xff0c; momo&#xff09;Drawcalls三角形数耗电量包体大小 二、 游戏体验 1. 直接体感 游戏花屏闪退卡顿延迟 2. 可能原因 内存超标Drawcall数量多FPS波动严重CPU占用高居不下…...

软考中级-数据库-3.3 数据结构-树

定义:树是n(n>=0)个结点的有限集合。当n=0时称为空树。在任一非空树中,有且仅有一个称为根的结点:其余结点可分为m(m>=0)个互不相交的有限集T1,T2,T3...,Tm…,其中每个集合又都是一棵树,并且称为根结点的子树。 树的相关概念 1、双亲、孩子和兄弟: 2、结点的度:一个结…...

typora高亮方案+鼠标侧键一键改色

引言 在typora里面有一个自定义的高亮, <mark></mark>>但是单一颜色就太难看了, 我使用人工智能, 搜索全网艺术家, 汇集了几种好看的格式,并且方便大家侧键一键 调用, 是不是太方便啦 ! 示例 午夜模式 春意盎然 深海蓝调 石墨文档 秋日暖阳 蜜桃宣言 使用方法 …...

【CSS】Tailwind CSS 与传统 CSS:设计理念与使用场景对比

1. 开发方式 1.1 传统 CSS 手写 CSS&#xff1a;你需要手动编写 CSS 规则&#xff0c;定义类名、ID 或元素选择器&#xff0c;并为每个元素编写样式。 分离式开发&#xff1a;HTML 和 CSS 通常是分离的&#xff0c;HTML 中通过类名或 ID 引用 CSS 文件中的样式。 示例&#…...

Linux(Centos 7.6)命令详解:vim

1.命令作用 vi/vim 是Linux 系统内置不可或缺的文本编辑命令&#xff0c;vim 是vi 的加强版本&#xff0c;兼容vi 的所有指令&#xff0c;不仅能编辑文本&#xff0c;而且还具有shell 程序编辑的功能&#xff0c;可以不同颜色的字体来辨别语法的正确性。 2.命令语法 usage: …...

记录一次wifi版有人物联串口服务器调试经过

1、首先买了一个华为的wifi路由器&#xff0c;连接上以后&#xff0c;设置好网络名字和wifi密码 2、用网线连接串口服务器&#xff0c;通过192.168.1.1登录&#xff0c;进行配置 找到无线客户端配置&#xff0c;先在基本配置中打开5G配置&#xff0c;然后再去5.8G配置中设置 …...

QWQ大模型评测榜单

评测榜单说明 在数学推理基准AIME24上&#xff0c;QwQ-32B达到了79.5分&#xff0c;几乎与DeepSeek-R1-617B的79.8分持平&#xff0c;远超OpenAI o1-mini的63.6分&#xff0c;及相同尺寸的R1蒸馏模型。 在编程能力方面&#xff0c;QwQ-32B 在LiveCodeBench上获得了63.4分&…...

【OSG学习笔记】Day 18: 碰撞检测与物理交互

物理引擎&#xff08;Physics Engine&#xff09; 物理引擎 是一种通过计算机模拟物理规律&#xff08;如力学、碰撞、重力、流体动力学等&#xff09;的软件工具或库。 它的核心目标是在虚拟环境中逼真地模拟物体的运动和交互&#xff0c;广泛应用于 游戏开发、动画制作、虚…...

MODBUS TCP转CANopen 技术赋能高效协同作业

在现代工业自动化领域&#xff0c;MODBUS TCP和CANopen两种通讯协议因其稳定性和高效性被广泛应用于各种设备和系统中。而随着科技的不断进步&#xff0c;这两种通讯协议也正在被逐步融合&#xff0c;形成了一种新型的通讯方式——开疆智能MODBUS TCP转CANopen网关KJ-TCPC-CANP…...

python如何将word的doc另存为docx

将 DOCX 文件另存为 DOCX 格式&#xff08;Python 实现&#xff09; 在 Python 中&#xff0c;你可以使用 python-docx 库来操作 Word 文档。不过需要注意的是&#xff0c;.doc 是旧的 Word 格式&#xff0c;而 .docx 是新的基于 XML 的格式。python-docx 只能处理 .docx 格式…...

css的定位(position)详解:相对定位 绝对定位 固定定位

在 CSS 中&#xff0c;元素的定位通过 position 属性控制&#xff0c;共有 5 种定位模式&#xff1a;static&#xff08;静态定位&#xff09;、relative&#xff08;相对定位&#xff09;、absolute&#xff08;绝对定位&#xff09;、fixed&#xff08;固定定位&#xff09;和…...

Matlab | matlab常用命令总结

常用命令 一、 基础操作与环境二、 矩阵与数组操作(核心)三、 绘图与可视化四、 编程与控制流五、 符号计算 (Symbolic Math Toolbox)六、 文件与数据 I/O七、 常用函数类别重要提示这是一份 MATLAB 常用命令和功能的总结,涵盖了基础操作、矩阵运算、绘图、编程和文件处理等…...

(转)什么是DockerCompose?它有什么作用?

一、什么是DockerCompose? DockerCompose可以基于Compose文件帮我们快速的部署分布式应用&#xff0c;而无需手动一个个创建和运行容器。 Compose文件是一个文本文件&#xff0c;通过指令定义集群中的每个容器如何运行。 DockerCompose就是把DockerFile转换成指令去运行。 …...

多种风格导航菜单 HTML 实现(附源码)

下面我将为您展示 6 种不同风格的导航菜单实现&#xff0c;每种都包含完整 HTML、CSS 和 JavaScript 代码。 1. 简约水平导航栏 <!DOCTYPE html> <html lang"zh-CN"> <head><meta charset"UTF-8"><meta name"viewport&qu…...

【VLNs篇】07:NavRL—在动态环境中学习安全飞行

项目内容论文标题NavRL: 在动态环境中学习安全飞行 (NavRL: Learning Safe Flight in Dynamic Environments)核心问题解决无人机在包含静态和动态障碍物的复杂环境中进行安全、高效自主导航的挑战&#xff0c;克服传统方法和现有强化学习方法的局限性。核心算法基于近端策略优化…...

人机融合智能 | “人智交互”跨学科新领域

本文系统地提出基于“以人为中心AI(HCAI)”理念的人-人工智能交互(人智交互)这一跨学科新领域及框架,定义人智交互领域的理念、基本理论和关键问题、方法、开发流程和参与团队等,阐述提出人智交互新领域的意义。然后,提出人智交互研究的三种新范式取向以及它们的意义。最后,总结…...

mac 安装homebrew (nvm 及git)

mac 安装nvm 及git 万恶之源 mac 安装这些东西离不开Xcode。及homebrew 一、先说安装git步骤 通用&#xff1a; 方法一&#xff1a;使用 Homebrew 安装 Git&#xff08;推荐&#xff09; 步骤如下&#xff1a;打开终端&#xff08;Terminal.app&#xff09; 1.安装 Homebrew…...