代码随想录27期|Python|Day38|509斐波那契|738.爬楼梯|746.746. 使用最小花费爬楼梯
贴一下动态规划的步骤(5步),就像是之前递归一样,需要每次落实到位。
- 确定dp数组(dp table)以及下标的含义
- 确定递推公式
- dp数组如何初始化
- 确定遍历顺序
- 举例推导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. 使用最小花费爬楼梯
贴一下动态规划的步骤(5步),就像是之前递归一样,需要每次落实到位。 确定dp数组(dp table)以及下标的含义确定递推公式dp数组如何初始化确定遍历顺序举例推导dp数组 509. 斐波那契 注意到n的范…...
windows docker容器部署前端项目
一、介绍 Docker 是一个开源的平台,旨在简化应用程序的开发、部署和运行。它通过使用容器(containers)来实现这一点。容器是一种轻量级、可移植的虚拟化方式,可以在不同的环境中一致地运行软件。 Docker 的主要作用和优点包括&a…...
科普文:微服务之全文检索ElasticSearch 集群的搭建
一、集群有什么用 1.1 群集的含义与产生 群集(或称为集群)是由多台主机构成,但对外,只表现为一个整体,只提供一个访问入口(域名或IP),相当于一台大型计算机。互联网应用中…...
QtObject是干什么的?
QtObject 是 Qt Quick 中的一个基类,用于创建非视觉对象。这意味着 QtObject 不渲染任何视觉内容,它主要用于定义数据和逻辑,而不是用户界面元素。你可以把 QtObject 看作是 QML 中的一个基础组件,用于创建和管理不需要显示的对象…...
锐捷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; }为…...
正则表达式测试工具
前言 正则表达式测试工具可供您输入正则表达式和测试文本,立即查看匹配结果. 下面是离线的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)】
⭐⭐⭐ 新老博友们,感谢各位的阅读观看 期末考试&假期调整暂时的停更了两个多月 没有写博客为大家分享优质内容 还容各位博友多多的理解 美丽的八月重生之我归来 继续为大家分享内容 你我共同加油 一起努力 ⭐⭐⭐ 数据结构将以顺序表、链表、栈区、队列、二叉树…...
前端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表格)
第一种:基于element表格分页 <template><!-- element分组打印 --><div class"hello"><button v-print"printContent">打印</button><div id"printDiv"><p>工资统计表</p><p>…...
搜维尔科技:借助 Xsens中的远程人体录制功能,可以在任何位置以无限量同时捕捉无限数量演员的身体动作
借助 Xsens中的远程人体录制功能,可以在任何位置以无限量同时捕捉无限数量演员的身体动作 搜维尔科技:借助 Xsens中的远程人体录制功能,可以在任何位置以无限量同时捕捉无限数量演员的身体动作...
2024/08 近期关于AI的阅读和理解[笔记]
#Cohere 就像商业能力很强的云数仓公司 Snowflake 一样,Cohere 也采用了按需付费模式而不是按月或按年付费,而且它的付费模式很精细。Cohere 按照模型的不同能力,包括文本生成,文本总结,重新排名,文本分类…...
SmartEDA:解锁设计新境界,从工具到灵感的飞跃之旅!
在这个数据驱动的时代,每一次点击、每一次滑动都蕴含着无限的可能与洞察。然而,在众多数据分析工具中,SmartEDA不仅仅是一把解锁数据奥秘的钥匙,它更是一座桥梁,连接着冰冷的数据世界与创意无限的设计灵感之源。今天&a…...
解决Minizip压缩后解压时的头部错误问题
最近,在处理文件压缩的任务时,我遇到了一个有趣的问题。使用Minizip库进行文件压缩后,在解压过程中收到了一个关于"头部错误"的警告。尽管这个警告看似令人担忧,但解压操作最终仍然能够成功完成文件的解压。这引发了我的…...
数据库表水平分割和垂直分割?
0.数据库表的水平分割和垂直分割是两种常见的数据库优化技术,它们分别针对不同的场景和需求进行数据表的拆分。 1. 水平分割(Horizontal Splitting)主要是按照记录进行分割,即不同的记录被分开保存在不同的表中&#x…...
Linux源码阅读笔记18-插入模型及删除模块操作
基础知识 模块是一种向Linux内核添加设备驱动程序、文件系统及其他组件的有效方法,不需要编译新内核 优点 通过使用模块,内核发布者能够预先编译大量驱动程序,而不会致使内核映像的尺寸发生膨胀。内核开发者可以将实验性的代码打包到模块中&a…...
力扣面试经典算法150题:移除元素
移除元素 今日的题目依旧是力扣面试经典算法150题中数组相关的题目:移除元素 题目链接:https://leetcode.cn/problems/remove-element/description/?envTypestudy-plan-v2&envIdtop-interview-150 题目描述 给定一个排序数组 nums 和一个值 val&a…...
java关于前端传布尔值后端接收一直为false问题
前端传值: {"message":"我肚子疼","isChiefComplaint": true }后端接收对象结构体: public class SymptomInquiryDTO {private String message;private boolean isChiefComplaint; }结果后端接收到的值一直是false&…...
工具学习_CVE Binary Tool
1. 工具概述 CVE Binary Tool 是一个免费的开源工具,可帮助您使用国家漏洞数据库(NVD)常见漏洞和暴露(CVE)列表中的数据以及Redhat、开源漏洞数据库(OSV)、Gitlab咨询数据库(GAD&am…...
【机器视觉】单目测距——运动结构恢复
ps:图是随便找的,为了凑个封面 前言 在前面对光流法进行进一步改进,希望将2D光流推广至3D场景流时,发现2D转3D过程中存在尺度歧义问题,需要补全摄像头拍摄图像中缺失的深度信息,否则解空间不收敛…...
生成 Git SSH 证书
🔑 1. 生成 SSH 密钥对 在终端(Windows 使用 Git Bash,Mac/Linux 使用 Terminal)执行命令: ssh-keygen -t rsa -b 4096 -C "your_emailexample.com" 参数说明: -t rsa&#x…...
【python异步多线程】异步多线程爬虫代码示例
claude生成的python多线程、异步代码示例,模拟20个网页的爬取,每个网页假设要0.5-2秒完成。 代码 Python多线程爬虫教程 核心概念 多线程:允许程序同时执行多个任务,提高IO密集型任务(如网络请求)的效率…...
C# 求圆面积的程序(Program to find area of a circle)
给定半径r,求圆的面积。圆的面积应精确到小数点后5位。 例子: 输入:r 5 输出:78.53982 解释:由于面积 PI * r * r 3.14159265358979323846 * 5 * 5 78.53982,因为我们只保留小数点后 5 位数字。 输…...
学校时钟系统,标准考场时钟系统,AI亮相2025高考,赛思时钟系统为教育公平筑起“精准防线”
2025年#高考 将在近日拉开帷幕,#AI 监考一度冲上热搜。当AI深度融入高考,#时间同步 不再是辅助功能,而是决定AI监考系统成败的“生命线”。 AI亮相2025高考,40种异常行为0.5秒精准识别 2025年高考即将拉开帷幕,江西、…...
Android第十三次面试总结(四大 组件基础)
Activity生命周期和四大启动模式详解 一、Activity 生命周期 Activity 的生命周期由一系列回调方法组成,用于管理其创建、可见性、焦点和销毁过程。以下是核心方法及其调用时机: onCreate() 调用时机:Activity 首次创建时调用。…...
NPOI操作EXCEL文件 ——CAD C# 二次开发
缺点:dll.版本容易加载错误。CAD加载插件时,没有加载所有类库。插件运行过程中用到某个类库,会从CAD的安装目录找,找不到就报错了。 【方案2】让CAD在加载过程中把类库加载到内存 【方案3】是发现缺少了哪个库,就用插件程序加载进…...
(一)单例模式
一、前言 单例模式属于六大创建型模式,即在软件设计过程中,主要关注创建对象的结果,并不关心创建对象的过程及细节。创建型设计模式将类对象的实例化过程进行抽象化接口设计,从而隐藏了类对象的实例是如何被创建的,封装了软件系统使用的具体对象类型。 六大创建型模式包括…...
C语言中提供的第三方库之哈希表实现
一. 简介 前面一篇文章简单学习了C语言中第三方库(uthash库)提供对哈希表的操作,文章如下: C语言中提供的第三方库uthash常用接口-CSDN博客 本文简单学习一下第三方库 uthash库对哈希表的操作。 二. uthash库哈希表操作示例 u…...
Chromium 136 编译指南 Windows篇:depot_tools 配置与源码获取(二)
引言 工欲善其事,必先利其器。在完成了 Visual Studio 2022 和 Windows SDK 的安装后,我们即将接触到 Chromium 开发生态中最核心的工具——depot_tools。这个由 Google 精心打造的工具集,就像是连接开发者与 Chromium 庞大代码库的智能桥梁…...
