2024/06/11--代码随想录算法1/17|理论基础、509. 斐波那契数、70. 爬楼梯、746. 使用最小花费爬楼梯

理论基础

在这里插入图片描述

动态规划:当前状态由前面的状态推导而来
贪心:局部选最优

动态规划5步曲

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

509. 斐波那契数

力扣链接
在这里插入图片描述

动态规划5步曲

  1. 确定dp数组(dp table)以及下标的含义:dp[i]是F(i)
  2. 确定递推公式,dp[i] = dp[i-1]+dp[i-2] i>1
  3. dp数组如何初始化 dp[0]=0 dp[1]=1
  4. 确定遍历顺序【从前往后】
  5. 举例推导dp数组

【动态规划】

时间复杂度:O(n) ,空间复杂度:O(n)
class Solution:def fib(self, n: int) -> int:if n == 0: return 0  #否则dp[1]就有问题dp = [0] * (n+1)dp[0] = 0dp[1] = 1for n in range(2,n+1):dp[n] = dp[n-1] + dp[n-2]return dp[n]	
#只用维护两个数值 ,时间复杂度:O(n) ,空间复杂度:O(1)
class Solution:def fib(self, n: int) -> int:if n <= 1 : return nprev1, prev2 = 0, 1for _ in range(2, n+1):cur = prev1 + prev2prev1, prev2 = prev2, curreturn prev2

【递归法】时间复杂度:O(2^n) ,空间复杂度:O(n)

class Solution:def fib(self, n: int) -> int:if n<2: return nreturn self.fib(n-1)+self.fib(n-2)

70. 爬楼梯

力扣链接
在这里插入图片描述

动态规划5步曲

  1. 确定dp数组(dp table)以及下标的含义: dp[i]:爬到第i个楼梯,有dp[i]种办法
  2. 确定递推公式,dp[i] = dp[i-1]+dp[i-2] i>1
  3. dp数组如何初始化 dp[1]=1 dp[2]=2
  4. 确定遍历顺序【从前往后】
  5. 举例推导dp数组
# 空间复杂度为O(n)版本
class Solution:def climbStairs(self, n: int) -> int:if n <= 1:return ndp = [0] * (n + 1)dp[1] = 1dp[2] = 2for i in range(3, n + 1):dp[i] = dp[i - 1] + dp[i - 2]return dp[n]
# 空间复杂度为O(1)版本
class Solution:def climbStairs(self, n: int) -> int:if n<3: return nprev1, prev2 = 1, 2for i in range(3,n+1):cur = prev1 + prev2prev1, prev2 = prev2, curreturn prev2

746. 使用最小花费爬楼梯

力扣链接
在这里插入图片描述

动态规划5步曲

  1. 确定dp数组(dp table)以及下标的含义:
    cost[i] :第 i 个阶梯对应着一个非负数的体力花费值;dp[i]:到达第i台阶所花费的最少体力
  2. 确定递推公式,dp[i] = min(dp[i-1]+cost[i-1], dp[i-2]+cost[i-2]) i>2
  3. dp数组如何初始化 dp[1]=cost[0] dp[2]=2
  4. 确定遍历顺序【从前往后】
  5. 举例推导dp数组

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:http://www.rhkb.cn/news/347025.html

如若内容造成侵权/违法违规/事实不符,请联系长河编程网进行投诉反馈email:809451989@qq.com,一经查实,立即删除!

相关文章

33.星号三角阵(二)

上海市计算机学会竞赛平台 | YACSYACS 是由上海市计算机学会于2019年发起的活动,旨在激发青少年对学习人工智能与算法设计的热情与兴趣,提升青少年科学素养,引导青少年投身创新发现和科研实践活动。https://www.iai.sh.cn/problem/742 题目描述 给定一个整数 𝑛,输出一个…

Linux用户,用户组,所有者权限分配,sftp用户权限分配

注意以下命令执行需要在root用户下执行 tenant命令切换至root命令 sudo -do root 删除用户信息 1.不删除用户主目录 userdel user_name 2.删除用户主目录 userdel -r user_name usermod命令修改用户账户权限 更改用户名 sudo usermod -l newusername oldusername 更…

QNX 7.0.0开发总结

1 QNX编译 1.1 基本概念 QNX可以直接使用Linux Makefile编译库和二进制&#xff0c;在Makefile文件中指定CCaarch64-unknown-nto-qnx7.0.0-g&#xff0c;或者CCx86_64-pc-nto-qnx7.0.0-g&#xff0c;保存退出后&#xff0c;运行source /qnx_sdk_path/qnxsdp-env.sh&#xff0c;…

React+TS前台项目实战(四)-- layout整体布局搭建

文章目录 前言一、Layout组件代码注释说明二、Content全局组件注释说明三、Header基础布局组件1. Header父级组件注释说明2. NavMenu导航子组件详细说明 四、效果展示总结 前言 本文主要讲Layout整体布局的构建以及全局内容盒子Content组件的使用。还包括了导航栏组件的基本封…

实现开源可商用的 ChatPDF RAG:密集向量检索(R)+上下文学习(AG)

实现 ChatPDF & RAG&#xff1a;密集向量检索&#xff08;R&#xff09;上下文学习&#xff08;AG&#xff09; RAG 是啥&#xff1f;实现 ChatPDF怎么优化 RAG&#xff1f; RAG 是啥&#xff1f; RAG 是检索增强生成的缩写&#xff0c;是一种结合了信息检索技术与语言生成…

python之点云数据读取与可视化

1、前言 将文件中点云数据进行读取进来&#xff0c;并进行数据处理&#xff0c;将处理后的点云数据进行可视化显示&#xff0c;是非常常见的操作。本博客介绍如何将文本形式的点云数据读取进来&#xff0c;并进行可视化展示。 2、点云可视化 点云可视化即将点云数据在三维空间…

亚马逊竞品分析之如何查找竞品

初选之后,要对产品进行竞品分析,查找竞品的方法: 1.Best Seller榜单查找 进入到该类目的BS榜单去找跟你选中的产品的竞品 看完BS榜单会找出一部分竞品 这个找相似也可以点击,是插件的一个以图搜图的功能,不过有的时候不太好使,某些同款产品可能搜不到。 Edge浏览器搭…

第7章 用户输入和 while 循环

第7章 用户输入和 while 循环 7.1 函数 input()的工作原理7.1.1 编写清晰的程序7.1.2 使用 int()来获取数值输入7.1.3 求模运算符 7.2 while 循环简介7.2.1 使用 while 循环7.2.2 让用户选择何时退出7.2.3 使用标志7.2.4 使用 break 退出循环7.2.5 在循环中使用 continue7.2.6 …

【Vue】Vuex概述

文章目录 一、使用场景二、优势三、注意 官网&#xff1a;https://vuex.vuejs.org/zh/ Vuex 是一个 Vue 的 状态管理工具&#xff0c;状态就是数据。 工具可以直接理解成插件 大白话&#xff1a;Vuex 是一个插件&#xff0c;可以帮我们管理 Vue 通用的数据 (多组件共享的数据)…

【Affine / Perspective Transformation】

文章目录 仿射变换介绍仿射变换 python 实现——cv2.warpAffine透视变换透视变换 python 实现——cv2.warpPerspective牛刀小试各类变换的区别与联系仿射变换和单应性矩阵透视变换和单应性矩阵 仿射变换介绍 仿射变换&#xff08;Affine Transformation&#xff09;&#xff0…

适配器模式和装饰器模式

文章目录 适配器模式1.引出适配器模式1.多功能转换插头2.基本介绍3.工作原理 2.类适配器1.基本介绍2.类图3.代码实现1.Voltage220V.java2.Voltage5V.java3.VoltageAdapter.java4.Phone.java5.Client.java6.结果 4.类适配器的注意事项 3.对象适配器1.基本介绍2.使用对象适配器改…

C51单片机 串口打印printf重定向

uart.c文件 #include "uart.h"void UartInit(void) //4800bps11.0592MHz {PCON | 0x80; //使能波特率倍速位SMODSCON 0x50; //8位数据,可变波特率。使能接收TMOD & 0x0F; //清除定时器1模式位TMOD | 0x20; //设定定时器1为8位自动重装方式TL1 0xF4; //设…

明天15点!如何打好重保预防针:迎战HVV经验分享

在当今数字化时代&#xff0c;网络攻击日益猖獗&#xff0c;各行各业面临的网络安全威胁不断升级。从钓鱼邮件到复杂的APT攻击&#xff0c;网络犯罪分子的手法层出不穷&#xff0c;给各行各业的信息安全带来了前所未有的挑战。 在这样的背景下&#xff0c;"HVV行动"应…

那些年我看过的技术书(持续更新,大佬的成长之路)

作为一个技术人啊&#xff0c;要学会多看书&#xff0c;发展自己。哦也&#xff01;你可以不关注&#xff0c;就把文章点个收藏吧&#xff0c;万一以后想看书了呢&#xff1f; 网络安全 CTF篇 入门篇 《极限黑客攻防&#xff1a;CTF赛题揭秘》 Web篇 Reserve篇 《IDApro…

ON DUPLICATE KEY UPDATE 子句

ON DUPLICATE KEY UPDATE 是 MySQL 中的一个 SQL 语句中的子句&#xff0c;主要用于在执行 INSERT 操作时处理可能出现的重复键值冲突。当尝试插入的记录导致唯一索引或主键约束冲突时&#xff08;即试图插入的记录的键值已经存在于表中&#xff09;&#xff0c;此子句会触发一…

virtual box安装invalid installation directory

问题原因 看官方文档Chapter 2. Installation Details 第2.1.2所示&#xff0c;安装目录需要满足两个条件&#xff1a; 一是&#xff1a;需要安装目录的所有父目录都要满足以下访问控制条件 Users S-1-5-32-545:(OI)(CI)(RX) Users S-1-5-32-545…

【Python列表解锁】:掌握序列精髓,驾驭动态数据集合

文章目录 &#x1f680;一、列表&#x1f308;二、常规操作&#x1f4a5;增&#x1f4a5;删&#x1f4a5;改&#x1f4a5;查 ⭐三、补充操作 &#x1f680;一、列表 列表是一个能够存储多个同一或不同元素的序列 列表&#xff1a;list ---- [] 列表属于序列类型&#xff08;容器…

ES升级--05--快照生成 和备份

提示&#xff1a;文章写完后&#xff0c;目录可以自动生成&#xff0c;如何生成可参考右边的帮助文档 文章目录 备份ES数据1.关闭集群自动均衡2.执行同步刷新3.停止集群节点的Elasticsearch服务4.修改Elasticsearch配置文件&#xff0c;开启快照功能&#xff0c;配置仓库目录为…

axure9设置组件自适应浏览器大小

问题&#xff1a;预览时不展示下方的滚动条 方法一&#xff1a;转化为动态面板 1.在页面上创建一个矩形 2.右键-转化为动态面板 3.双击进入动态面板设置 4.设置动态面板矩形的颜色 5.删除原来的矩形 6.关闭动态面板&#xff0c;点击预览 7.此时可以发现底部没有滚动条了 方法…

Java进阶_多态特性

生活中的多态 多态是同一个行为具有多个不同表现形式或形态的能力。多态就是同一个接口&#xff0c;使用不同的实例而执行不同操作&#xff0c;如图所示&#xff1a; 现实中&#xff0c;比如我们按下 F1 键这个动作&#xff0c;同一个事件发生在不同的对象上会产生不同的结果。…