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

算法记录 | Day38 动态规划

对于动态规划问题,将拆解为如下五步曲

  1. 确定dp数组(dp table)以及下标的含义
  2. 确定递推公式
  3. dp数组如何初始化
  4. 确定遍历顺序
  5. 举例推导dp数组

509.斐波那契数

思路:

  1. 确定dp数组(dp table)以及下标的含义:dp[i]的定义为:第i个数的斐波那契数值是dp[i]

  2. 确定递推公式:状态转移方程 dp[i] = dp[i - 1] + dp[i - 2]

  3. dp数组如何初始化:dp[0] = 0,dp[1] = 1

  4. 确定遍历顺序:从前到后遍历

  5. 举例推导dp数组:推导一下,当N为10的时候,dp数组应该是如下的数列:

    0 1 1 2 3 5 8 13 21 34 55

class Solution:def fib(self, n: int) -> int:dp = [0 for _ in range(n+1)]if n < 1:return 0dp[0] = 0dp[1] = 1for i in range(2,n+1):dp[i] = dp[i-1] + dp[i-2]return dp[n]

70.爬楼梯

思路:

  1. 确定dp数组(dp table)以及下标的含义:dp[i]: 爬到第i层楼梯,有dp[i]种方法

  2. 确定递推公式:

    dp[i] 可以有两个方向推出来。

    首先是dp[i - 1],上i-1层楼梯,有dp[i - 1]种方法,那么再一步跳一个台阶不就是dp[i]了么。

    还有就是dp[i - 2],上i-2层楼梯,有dp[i - 2]种方法,那么再一步跳两个台阶不就是dp[i]了么。

  3. dp数组如何初始化:dp[0] = 1,dp[1] = 1

  4. 确定遍历顺序:从前到后遍历

  5. 举例推导dp数组:

class Solution:def climbStairs(self, n: int) -> int:dp = [0 for _ in range(n+1)]if n == 0:return 0dp[0] = 1dp[1] = 1for i in range(2,n+1):dp[i] = dp[i-1] + dp[i-2]return dp[n]

746.使用最小花费爬楼梯

思路:

  1. 确定dp数组(dp table)以及下标的含义:dp[i]爬到楼顶的花费

  2. 确定递推公式:

    dp[i - 1],到上i-1层楼梯,花费dp[i - 1],i-1到i花费dp[i - 1]+cost[i-1]

    dp[i - 2],上i-2层楼梯,花费dp[i - 2],i-2到i花费dp[i - 2]+cost[i-2]

    dp [i] = min(dp[i - 1]+cost[i-1],dp[i - 2]+cost[i-2])

  3. dp数组如何初始化:dp[0] = 0,dp[1] = 0

    **注意:**题目描述中明确说了 “你可以选择从下标为 0 或下标为 1 的台阶开始爬楼梯。” 也就是说 从 到达 第 0 个台阶是不花费的,但从 第0 个台阶 往上跳的话,需要花费 cost[0]。

  4. 确定遍历顺序:从前到后遍历

  5. 举例推导dp数组:

cost = [1, 100, 1, 1, 1, 100, 1, 1, 100, 1] ,来模拟一下dp数组的状态变化,如下:

img

class Solution:def minCostClimbingStairs(self, cost: List[int]) -> int:n = len(cost) dp = [0 for _  in range(n+1)]if n < 1:return 0dp[0] = 0dp[1] = 0for i in range(2, n+1):dp[i] = min(dp[i-1]+cost[i-1],dp[i-2]+cost[i-2])return dp[n]

相关文章:

算法记录 | Day38 动态规划

对于动态规划问题&#xff0c;将拆解为如下五步曲 确定dp数组&#xff08;dp table&#xff09;以及下标的含义确定递推公式dp数组如何初始化确定遍历顺序举例推导dp数组 509.斐波那契数 思路&#xff1a; 确定dp数组&#xff08;dp table&#xff09;以及下标的含义&#x…...

PMP项目管理-[第六章]进度管理

进度管理知识体系&#xff1a; 规划进度管理&#xff1a; 定义活动&#xff1a; 排列活动顺序&#xff1a; 估算活动持续时间&#xff1a; 制定进度计划&#xff1a; 6.1 规划进度管理 定义&#xff1a;为规划、编制、管理、执行和控制项目进度而制定政策、程序和文档的过程 作…...

Python变量

一、变量的定义 变量名的命名规范&#xff1a;变量名是标识符的一种&#xff0c;变量名不能随便起&#xff0c;要遵守 Python 标识符命名规范。 ## 常用的命名规范有以下几种&#xff1a; 1. 变量名为单个单词的话全部小写 name "张三" 2. 多个单词组成的话&#…...

准备换工作的看过来~

大家好&#xff0c;最近有不少小伙伴在后台留言&#xff0c;得准备面试了&#xff0c;又不知道从何下手&#xff01;为了帮大家节约时间&#xff0c;特意准备了一份面试相关的资料&#xff0c;内容非常的全面&#xff0c;真的可以好好补一补&#xff0c;希望大家在都能拿到理想…...

免费AI人工智能在线写作伪原创-百度ai自动写文章

免费伪原创洗稿工具 免费伪原创洗稿工具现在终于推出了&#xff01;你是否在写作的时候&#xff0c;经常因为缺乏灵感而苦恼&#xff1f;或者&#xff0c;你在撰写文章的时候&#xff0c;发现自己的语言表述不够丰富&#xff0c;缺乏变化&#xff0c;语句重复率太高&#xff1f…...

互联网摸鱼日报(2023-04-21)

互联网摸鱼日报&#xff08;2023-04-21&#xff09; InfoQ 热门话题 3年不用云能节省4亿美元&#xff01;想知道我们为什么敢不用AWS吗&#xff1f; 华为周红&#xff1a;通过行业大模型促进AI价值创造 建设业务规划、交付和反馈闭环&#xff5c; BizDevOps 公开课 云原生时…...

5.3、web服务器简介HTTP协议

代码地址 5.3、web服务器简介HTTP协议 1.Web-Server&#xff08;网页服务器&#xff09;2.HTTP协议(应用层的协议)①简介②概述③工作原理④HTTP请求报文格式⑤HTTP响应报文格式⑥HTTP请求方法⑦HTTP状态码 1.Web-Server&#xff08;网页服务器&#xff09; 一个 Web Server …...

【观察】华为:新一代楼宇网络,使能绿建智慧化

“碳达峰”、“碳中和”目标是我国生态文明建设和高质量可持续发展的重要战略安排&#xff0c;将推动全社会加速向绿色低碳转型。作为全球既有建筑和每年新建建筑量最大的国家&#xff0c;大力发展绿色建筑对中国全方位迈向低碳社会、实现高质量发展具有重要意义。 《“十四五”…...

【C# .NET】chapter 13 使用多任务改进性能和可扩展性

目录 一、物理内存和虚拟内存使用&#xff08;Recorder 类&#xff09; 二、 对比 string的“”操作与stringbuilder 操作 的处理效率&#xff0c;内存消耗情况&#xff0c; 三、异步运行任务、三种启动任务方法、将上一任务方法处理结果作为参数传给下一任务方法 四、嵌套…...

CA(证书颁发机构)

CA 根证书路径/csk-rootca/csk-ca.pem&#xff1b; ~ 签发数字证书&#xff0c;颁发者信息&#xff1a;(仅包含如下信息) C CN ST China L BeiJing O skills OU Operations Departments CN CSK Global Root CA 1.修改证书的路径以及相关配置 vi /etc/pki/tls/op…...

辛弃疾最有代表性的十首词

辛弃疾的词&#xff0c;风格多样&#xff0c;题材广阔&#xff0c;几乎涉及到生活中的各个方面&#xff0c;从爱国情怀到日常生活&#xff0c;甚至连戒酒这种事都能写入词中。辛弃疾也是两宋词人中&#xff0c;存词最多的作家之一&#xff0c;现存的六百多首作品。 辛弃疾的词…...

MC9S12G128开发板—实现按键发送CAN报文指示小车移动功能

实验环境&#xff1a;MC9S12G128开发板 基本功能&#xff1a;控制开发板上的按键&#xff0c;模拟车辆移动的上下左右四个方位&#xff0c;通过can通信告诉上位机界面&#xff0c;车辆轨迹的移动方位。 1. 1939报文发送的示例代码 MC9S12G128开发板1939协议发送can报文数据的…...

尚融宝22-提交借款申请

目录 一、需求介绍 二、图片上传 &#xff08;一&#xff09;前端页面 &#xff08;二&#xff09;实现图片上传 三、数据字典展示 &#xff08;一&#xff09;后端 &#xff08;二&#xff09;前端 四、表单信息提交 &#xff08;一&#xff09;后端 1、VO对象&…...

机器学习在生态、环境经济学中的实践技术应用及论文写作

近年来&#xff0c;人工智能领域已经取得突破性进展&#xff0c;对经济社会各个领域都产生了重大影响&#xff0c;结合了统计学、数据科学和计算机科学的机器学习是人工智能的主流方向之一&#xff0c;目前也在飞快的融入计量经济学研究。表面上机器学习通常使用大数据&#xf…...

Android硬件通信之 WIFI通信

一&#xff0c;简介 1.1 随着网络的普及和通信技术的发展&#xff0c;网络的传输速度也越来越快&#xff0c;wifi技术也还成为手机设备最基本的配置。我们可以通过wifi实现手机与手机之前的信息传输&#xff0c;当然也可以与任意一台有wifi模块的其它设备传输。 1.2 wifi与蓝…...

面试官:“请描述一下Android系统的启动流程”

作者&#xff1a;OpenGL 前言 什么是Android启动流程呢&#xff1f;其实指的就是我们Android系统从按下电源到显示界面的整个过程。 当我们把手机充好电&#xff0c;按下电源&#xff0c;手机会弹出相应启动界面&#xff0c;在等了一段时间之后&#xff0c;会弹出我们熟悉的主…...

k8s delete node 后 重启kubelet会自己加入到集群 ?

原因 当执行kubectl delete node命令时&#xff0c;Kubernetes API服务器会收到该节点的删除请求&#xff0c;并将其从集群中删除。此时&#xff0c;kubelet服务在该节点上仍然在运行&#xff0c;但已经不再与集群通信。 当您重启kubelet服务时&#xff0c;它会重新向API服务…...

REXROTH液压方向阀安装须知

安装规程 阀安装到系统之前&#xff0c;应该对照订货型号比较其型号说明。 确认阀的连接表面和底板无水分&#xff0c;没有油。 &#xff0d; 清洁&#xff1a; ‧ 安装元件时&#xff0c;确认工业阀和周围干净 ‧ 油箱须密闭&#xff0c;以防止外部污染 ‧ 安装之前&…...

【数据结构实验】哈夫曼树

【数据结构实验】哈夫曼树 简介&#xff1a; 为一个信息收发站编写一个哈夫曼码的编/译码系统。文末贴出了源代码。 需求分析 完整的系统需要具备完整的功能&#xff0c;包含初始化、编码、译码、印代码文件和印哈夫曼树&#xff0c;因此需要进行相应的文件操作进行配合。哈…...

浏览器不好用?插件来帮忙

一、目的 浏览器本身具备的功能并不完善&#xff0c;不同的用户可以为自己浏览器增加想要功能&#xff0c;使得浏览器更能符合自己的需求&#xff0c;提高浏览器使用的舒适度 二、推荐插件 AdblockPlus LastPass&#xff08;密码记录&#xff0c;全平台通用&#xff09; Dar…...

XCTF-web-easyupload

试了试php&#xff0c;php7&#xff0c;pht&#xff0c;phtml等&#xff0c;都没有用 尝试.user.ini 抓包修改将.user.ini修改为jpg图片 在上传一个123.jpg 用蚁剑连接&#xff0c;得到flag...

装饰模式(Decorator Pattern)重构java邮件发奖系统实战

前言 现在我们有个如下的需求&#xff0c;设计一个邮件发奖的小系统&#xff0c; 需求 1.数据验证 → 2. 敏感信息加密 → 3. 日志记录 → 4. 实际发送邮件 装饰器模式&#xff08;Decorator Pattern&#xff09;允许向一个现有的对象添加新的功能&#xff0c;同时又不改变其…...

UE5 学习系列(三)创建和移动物体

这篇博客是该系列的第三篇&#xff0c;是在之前两篇博客的基础上展开&#xff0c;主要介绍如何在操作界面中创建和拖动物体&#xff0c;这篇博客跟随的视频链接如下&#xff1a; B 站视频&#xff1a;s03-创建和移动物体 如果你不打算开之前的博客并且对UE5 比较熟的话按照以…...

数据链路层的主要功能是什么

数据链路层&#xff08;OSI模型第2层&#xff09;的核心功能是在相邻网络节点&#xff08;如交换机、主机&#xff09;间提供可靠的数据帧传输服务&#xff0c;主要职责包括&#xff1a; &#x1f511; 核心功能详解&#xff1a; 帧封装与解封装 封装&#xff1a; 将网络层下发…...

Linux C语言网络编程详细入门教程:如何一步步实现TCP服务端与客户端通信

文章目录 Linux C语言网络编程详细入门教程&#xff1a;如何一步步实现TCP服务端与客户端通信前言一、网络通信基础概念二、服务端与客户端的完整流程图解三、每一步的详细讲解和代码示例1. 创建Socket&#xff08;服务端和客户端都要&#xff09;2. 绑定本地地址和端口&#x…...

Java + Spring Boot + Mybatis 实现批量插入

在 Java 中使用 Spring Boot 和 MyBatis 实现批量插入可以通过以下步骤完成。这里提供两种常用方法&#xff1a;使用 MyBatis 的 <foreach> 标签和批处理模式&#xff08;ExecutorType.BATCH&#xff09;。 方法一&#xff1a;使用 XML 的 <foreach> 标签&#xff…...

C++:多态机制详解

目录 一. 多态的概念 1.静态多态&#xff08;编译时多态&#xff09; 二.动态多态的定义及实现 1.多态的构成条件 2.虚函数 3.虚函数的重写/覆盖 4.虚函数重写的一些其他问题 1&#xff09;.协变 2&#xff09;.析构函数的重写 5.override 和 final关键字 1&#…...

音视频——I2S 协议详解

I2S 协议详解 I2S (Inter-IC Sound) 协议是一种串行总线协议&#xff0c;专门用于在数字音频设备之间传输数字音频数据。它由飞利浦&#xff08;Philips&#xff09;公司开发&#xff0c;以其简单、高效和广泛的兼容性而闻名。 1. 信号线 I2S 协议通常使用三根或四根信号线&a…...

RabbitMQ入门4.1.0版本(基于java、SpringBoot操作)

RabbitMQ 一、RabbitMQ概述 RabbitMQ RabbitMQ最初由LShift和CohesiveFT于2007年开发&#xff0c;后来由Pivotal Software Inc.&#xff08;现为VMware子公司&#xff09;接管。RabbitMQ 是一个开源的消息代理和队列服务器&#xff0c;用 Erlang 语言编写。广泛应用于各种分布…...

【堆垛策略】设计方法

堆垛策略的设计是积木堆叠系统的核心&#xff0c;直接影响堆叠的稳定性、效率和容错能力。以下是分层次的堆垛策略设计方法&#xff0c;涵盖基础规则、优化算法和容错机制&#xff1a; 1. 基础堆垛规则 (1) 物理稳定性优先 重心原则&#xff1a; 大尺寸/重量积木在下&#xf…...