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

代码随想录27期|Python|Day38|509斐波那契|738.爬楼梯|746.746. 使用最小花费爬楼梯

 贴一下动态规划的步骤(5步),就像是之前递归一样,需要每次落实到位。

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

​​​​​509. 斐波那契

注意到n的范围是30以内,一个更快的方法是直接把这个数组先算出来,然后直接取。

class Solution(object):def fib(self, n):""":type n: int:rtype: int"""fib_list = self.pre_print()return fib_list[n]def pre_print(self):fib_list = [0, 1, 1]for i in range(3, 31):fib_list.append(fib_list[i-2] + fib_list[i-1])return fib_list

当然可以使用递归: 

class Solution(object):def fib(self, n):""":type n: int:rtype: int"""## 递归解法if n < 2:return nelse:return self.fib(n-1) + self.fib(n-2)

70. 爬楼梯

在规定了每次只能走1或者2步的时候,本题的本质就是求解斐波那契鹅数列。

可以看到,dp[i]在第三位开始,往前看一位dp[i-1],只有一种情况(就是走1步),往前看两位dp[i-2],只有一种情况(就是走2步,因为走1步的已经算在dp[i-1]里面了)

所以dp[i]=dp[i-1]+dp[i-2]

则自然可以看出是斐波那契。

关于dp[0]的初始化:由于题目说是从1开始,所以0直接排除了。但是对于一般的动态规划为题(如之前的斐波那契),都需要考虑0的初始化。本题直接初始化dp[1]=1,dp[2]=2即可。

class Solution(object):def climbStairs(self, n):""":type n: int:rtype: int"""if n <= 2:return n# 初始化dp = [0] * 3dp[1] = 1dp[2] = 2  # 实际上只用到了2个位置# 推倒关系for i in range(3, n+1):  # 注意i开始和结束的值total = dp[1] + dp[2]dp[1] = dp[2]dp[2] = totalreturn dp[2]

746. 使用最小花费爬楼梯

本题关键在于如何确定dp数组和下标的含义。

1、确定dp数组和下标的含义:数组的第i个代表走到第i个所需要的最小花费;

2、初始化:由于0和1不需要花费,所以dp都是0;

3、递推:当前i个的最小花费是取决于前2个dp值和cost的值,取和的最小值。

class Solution(object):def minCostClimbingStairs(self, cost):""":type cost: List[int]:rtype: int"""dp = [0] * (len(cost)+1)dp[0], dp[1] = 0, 0for i in range(2, len(dp)):dp[i] = min(dp[i-1] + cost[i-1], dp[i-2] + cost[i-2])return dp[-1] 

Day38完结!!!

相关文章:

代码随想录27期|Python|Day38|509斐波那契|738.爬楼梯|746.746. 使用最小花费爬楼梯

贴一下动态规划的步骤&#xff08;5步&#xff09;&#xff0c;就像是之前递归一样&#xff0c;需要每次落实到位。 确定dp数组&#xff08;dp table&#xff09;以及下标的含义确定递推公式dp数组如何初始化确定遍历顺序举例推导dp数组 ​​​​​509. 斐波那契 注意到n的范…...

windows docker容器部署前端项目

一、介绍 Docker 是一个开源的平台&#xff0c;旨在简化应用程序的开发、部署和运行。它通过使用容器&#xff08;containers&#xff09;来实现这一点。容器是一种轻量级、可移植的虚拟化方式&#xff0c;可以在不同的环境中一致地运行软件。 Docker 的主要作用和优点包括&a…...

科普文:微服务之全文检索ElasticSearch 集群的搭建

一、集群有什么用 1.1 群集的含义与产生 群集&#xff08;或称为集群&#xff09;是由多台主机构成&#xff0c;但对外&#xff0c;只表现为一个整体&#xff0c;只提供一个访问入口&#xff08;域名或IP&#xff09;&#xff0c;相当于一台大型计算机。互联网应用中&#xf…...

QtObject是干什么的?

QtObject 是 Qt Quick 中的一个基类&#xff0c;用于创建非视觉对象。这意味着 QtObject 不渲染任何视觉内容&#xff0c;它主要用于定义数据和逻辑&#xff0c;而不是用户界面元素。你可以把 QtObject 看作是 QML 中的一个基础组件&#xff0c;用于创建和管理不需要显示的对象…...

锐捷RCNA | 远程登录与路由技术

锐捷RCNA | 远程登录与路由技术 一、远程登录配置1. Telnet远程登录介绍2. 案例1--设置远程登录密码实现远程登录3. 案例2--定义不同用户账户实现远程用户权限隔离4. SSH远程登录介绍5. 案例--通过SSH功能远程管理设备 二、路由技术1. 直连路由的数据通信2. 间接路由的数据通信…...

实现Vue-tiny-diff算法

前言 前面我们实现了基本的数据更新到视图渲染的逻辑,但是这种方式(innerHTML)是极其低效的, 因此,我们相应引入 dom 和 diff 算法, 数据到视图的过程变为: state -> vdom -> dom vNode 层 所谓 vNode, 就是一个表示 dom 结构的轻量对象 {tag, props, children; }为…...

正则表达式测试工具

前言 正则表达式测试工具可供您输入正则表达式和测试文本&#xff0c;立即查看匹配结果. 下面是离线的HTML文件,同样可以提供相同的服务. 目录 使用说明 HTML代码 正则表达式的编写经验和方法 总结 使用说明 1.先将HTML代码存储成.html为后缀的文件; 2.然后用浏览器打开这个…...

Github 2024-08-02 开源项目日报 Top9

根据Github Trendings的统计,今日(2024-08-02统计)共有9个项目上榜。根据开发语言中项目的数量,汇总情况如下: 开发语言项目数量Python项目4Go项目1C项目1Rust项目1Shell项目1Dockerfile项目1TypeScript项目1Dart项目1Docker-OSX: 在Docker容器中运行Mac OS X 创建周期:152…...

重生之我 学习【数据结构之顺序表(SeqList)】

⭐⭐⭐ 新老博友们&#xff0c;感谢各位的阅读观看 期末考试&假期调整暂时的停更了两个多月 没有写博客为大家分享优质内容 还容各位博友多多的理解 美丽的八月重生之我归来 继续为大家分享内容 你我共同加油 一起努力 ⭐⭐⭐ 数据结构将以顺序表、链表、栈区、队列、二叉树…...

前端day4-表单标签

<!DOCTYPE html> <html lang"en"> <head><meta charset"UTF-8"><meta name"viewport" content"widthdevice-width, initial-scale1.0"><title>day4-表单</title> </head> <body&g…...

vue3-print-nb 表格打印分页,第一页有空白的情况出现解决方法(两种:一种原生,一种基于element表格)

第一种&#xff1a;基于element表格分页 <template><!-- element分组打印 --><div class"hello"><button v-print"printContent">打印</button><div id"printDiv"><p>工资统计表</p><p>…...

搜维尔科技:借助 Xsens中的远程人体录制功能,可以在任何位置以无限量同时捕捉无限数量演员的身体动作

借助 Xsens中的远程人体录制功能&#xff0c;可以在任何位置以无限量同时捕捉无限数量演员的身体动作 搜维尔科技&#xff1a;借助 Xsens中的远程人体录制功能&#xff0c;可以在任何位置以无限量同时捕捉无限数量演员的身体动作...

2024/08 近期关于AI的阅读和理解[笔记]

#Cohere 就像商业能力很强的云数仓公司 Snowflake 一样&#xff0c;Cohere 也采用了按需付费模式而不是按月或按年付费&#xff0c;而且它的付费模式很精细。Cohere 按照模型的不同能力&#xff0c;包括文本生成&#xff0c;文本总结&#xff0c;重新排名&#xff0c;文本分类…...

SmartEDA:解锁设计新境界,从工具到灵感的飞跃之旅!

在这个数据驱动的时代&#xff0c;每一次点击、每一次滑动都蕴含着无限的可能与洞察。然而&#xff0c;在众多数据分析工具中&#xff0c;SmartEDA不仅仅是一把解锁数据奥秘的钥匙&#xff0c;它更是一座桥梁&#xff0c;连接着冰冷的数据世界与创意无限的设计灵感之源。今天&a…...

解决Minizip压缩后解压时的头部错误问题

最近&#xff0c;在处理文件压缩的任务时&#xff0c;我遇到了一个有趣的问题。使用Minizip库进行文件压缩后&#xff0c;在解压过程中收到了一个关于"头部错误"的警告。尽管这个警告看似令人担忧&#xff0c;但解压操作最终仍然能够成功完成文件的解压。这引发了我的…...

数据库表水平分割和垂直分割?

0.数据库表的水平分割和垂直分割是两种常见的数据库优化技术&#xff0c;‌它们分别针对不同的场景和需求进行数据表的拆分。‌ 1. 水平分割&#xff08;‌Horizontal Splitting&#xff09;‌主要是按照记录进行分割&#xff0c;‌即不同的记录被分开保存在不同的表中&#x…...

Linux源码阅读笔记18-插入模型及删除模块操作

基础知识 模块是一种向Linux内核添加设备驱动程序、文件系统及其他组件的有效方法&#xff0c;不需要编译新内核 优点 通过使用模块&#xff0c;内核发布者能够预先编译大量驱动程序&#xff0c;而不会致使内核映像的尺寸发生膨胀。内核开发者可以将实验性的代码打包到模块中&a…...

力扣面试经典算法150题:移除元素

移除元素 今日的题目依旧是力扣面试经典算法150题中数组相关的题目&#xff1a;移除元素 题目链接&#xff1a;https://leetcode.cn/problems/remove-element/description/?envTypestudy-plan-v2&envIdtop-interview-150 题目描述 给定一个排序数组 nums 和一个值 val&a…...

java关于前端传布尔值后端接收一直为false问题

前端传值&#xff1a; {"message":"我肚子疼","isChiefComplaint": true }后端接收对象结构体&#xff1a; public class SymptomInquiryDTO {private String message;private boolean isChiefComplaint; }结果后端接收到的值一直是false&…...

工具学习_CVE Binary Tool

1. 工具概述 CVE Binary Tool 是一个免费的开源工具&#xff0c;可帮助您使用国家漏洞数据库&#xff08;NVD&#xff09;常见漏洞和暴露&#xff08;CVE&#xff09;列表中的数据以及Redhat、开源漏洞数据库&#xff08;OSV&#xff09;、Gitlab咨询数据库&#xff08;GAD&am…...

从零实现富文本编辑器#5-编辑器选区模型的状态结构表达

先前我们总结了浏览器选区模型的交互策略&#xff0c;并且实现了基本的选区操作&#xff0c;还调研了自绘选区的实现。那么相对的&#xff0c;我们还需要设计编辑器的选区表达&#xff0c;也可以称为模型选区。编辑器中应用变更时的操作范围&#xff0c;就是以模型选区为基准来…...

Linux相关概念和易错知识点(42)(TCP的连接管理、可靠性、面临复杂网络的处理)

目录 1.TCP的连接管理机制&#xff08;1&#xff09;三次握手①握手过程②对握手过程的理解 &#xff08;2&#xff09;四次挥手&#xff08;3&#xff09;握手和挥手的触发&#xff08;4&#xff09;状态切换①挥手过程中状态的切换②握手过程中状态的切换 2.TCP的可靠性&…...

优选算法第十二讲:队列 + 宽搜 优先级队列

优选算法第十二讲&#xff1a;队列 宽搜 && 优先级队列 1.N叉树的层序遍历2.二叉树的锯齿型层序遍历3.二叉树最大宽度4.在每个树行中找最大值5.优先级队列 -- 最后一块石头的重量6.数据流中的第K大元素7.前K个高频单词8.数据流的中位数 1.N叉树的层序遍历 2.二叉树的锯…...

重启Eureka集群中的节点,对已经注册的服务有什么影响

先看答案&#xff0c;如果正确地操作&#xff0c;重启Eureka集群中的节点&#xff0c;对已经注册的服务影响非常小&#xff0c;甚至可以做到无感知。 但如果操作不当&#xff0c;可能会引发短暂的服务发现问题。 下面我们从Eureka的核心工作原理来详细分析这个问题。 Eureka的…...

wpf在image控件上快速显示内存图像

wpf在image控件上快速显示内存图像https://www.cnblogs.com/haodafeng/p/10431387.html 如果你在寻找能够快速在image控件刷新大图像&#xff08;比如分辨率3000*3000的图像&#xff09;的办法&#xff0c;尤其是想把内存中的裸数据&#xff08;只有图像的数据&#xff0c;不包…...

零知开源——STM32F103RBT6驱动 ICM20948 九轴传感器及 vofa + 上位机可视化教程

STM32F1 本教程使用零知标准板&#xff08;STM32F103RBT6&#xff09;通过I2C驱动ICM20948九轴传感器&#xff0c;实现姿态解算&#xff0c;并通过串口将数据实时发送至VOFA上位机进行3D可视化。代码基于开源库修改优化&#xff0c;适合嵌入式及物联网开发者。在基础驱动上新增…...

【FTP】ftp文件传输会丢包吗?批量几百个文件传输,有一些文件没有传输完整,如何解决?

FTP&#xff08;File Transfer Protocol&#xff09;本身是一个基于 TCP 的协议&#xff0c;理论上不会丢包。但 FTP 文件传输过程中仍可能出现文件不完整、丢失或损坏的情况&#xff0c;主要原因包括&#xff1a; ✅ 一、FTP传输可能“丢包”或文件不完整的原因 原因描述网络…...

Redis上篇--知识点总结

Redis上篇–解析 本文大部分知识整理自网上&#xff0c;在正文结束后都会附上参考地址。如果想要深入或者详细学习可以通过文末链接跳转学习。 1. 基本介绍 Redis 是一个开源的、高性能的 内存键值数据库&#xff0c;Redis 的键值对中的 key 就是字符串对象&#xff0c;而 val…...

CSS 工具对比:UnoCSS vs Tailwind CSS,谁是你的菜?

在现代前端开发中&#xff0c;Utility-First (功能优先) CSS 框架已经成为主流。其中&#xff0c;Tailwind CSS 无疑是市场的领导者和标杆。然而&#xff0c;一个名为 UnoCSS 的新星正以其惊人的性能和极致的灵活性迅速崛起。 这篇文章将深入探讨这两款工具的核心理念、技术差…...

基于小程序老人监护管理系统源码数据库文档

摘 要 近年来&#xff0c;随着我国人口老龄化问题日益严重&#xff0c;独居和居住养老机构的的老年人数量越来越多。而随着老年人数量的逐步增长&#xff0c;随之而来的是日益突出的老年人问题&#xff0c;尤其是老年人的健康问题&#xff0c;尤其是老年人产生健康问题后&…...