【特殊子序列 DP】力扣509. 斐波那契数
斐波那契数 (通常用 F(n) 表示)形成的序列称为 斐波那契数列 。该数列由 0 和 1 开始,后面的每一项数字都是前面两项数字的和。也就是:
F(0) = 0,F(1) = 1
F(n) = F(n - 1) + F(n - 2),其中 n > 1
给定 n ,请计算 F(n) 。
示例 1:
输入:n = 2
输出:1
解释:F(2) = F(1) + F(0) = 1 + 0 = 1
示例 2:
输入:n = 3
输出:2
解释:F(3) = F(2) + F(1) = 1 + 1 = 2
示例 3:
输入:n = 4
输出:3
解释:F(4) = F(3) + F(2) = 2 + 1 = 3
提示:
0 <= n <= 30
动态规划
class Solution {
public:int fib(int n) {vector<int> dp(n + 1);if(n == 0) return 0;if(n == 1) return 1;dp[0] = 0, dp[1] = 1;for(int i = 2; i <= n; i++){ dp[i] = dp[i-1] + dp[i-2];}return dp[n];}
};
时间复杂度:O(n)。
空间复杂度:O(n)。
定义一个数组dp[i]代表f(n)的值,然后得出状态转移方程 dp[i] = dp[i-1] + dp[i-2],最后返回dp[n]即可。
相关文章:
【特殊子序列 DP】力扣509. 斐波那契数
斐波那契数 (通常用 F(n) 表示)形成的序列称为 斐波那契数列 。该数列由 0 和 1 开始,后面的每一项数字都是前面两项数字的和。也就是: F(0) 0,F(1) 1 F(n) F(n - 1) F(n - 2),其中 n > 1 给定 n &…...
linux 架构详解
Linux 是一种开源的操作系统内核,最初由 Linus Torvalds 于 1991 年创建。它是一个基于 Unix 的操作系统内核,用于构建完整的操作系统。Linux 架构是指 Linux 操作系统的内部结构和组成组件的工作方式。 整体架构 Linux系统通常被看作是一个层次化的结…...
Spring Data Elasticsearch
简介说明 spring-data-elasticsearch是比较好用的一个elasticsearch客户端,本文介绍如何使用它来操作ES。本文使用spring-boot-starter-data-elasticsearch,它内部会引入spring-data-elasticsearch。 Spring Data ElasticSearch有下边这几种方法操作El…...
OpenGL编译用户着色器shader
shader相信很多朋友们都听说过,shader就是运行再GPU上的程序。虽然是这么说,但是我们发现,很多IDE开发工具比如说visual studio 没有办法直接去运行shader代码。这是因为,许多编译器不会自动将shader文件编译成可执行的代码然后发…...
过期策略、内存淘汰机制
1.过期策略:请求时删除 定期删除 请求时删除:使用key之前,检查是否过期,属于一种被动的处理方式。 因此,过期时间到了不表示这个key真的被删除了 定期删除:Redis默认每隔100ms检查,有过期ke…...
Scala的正则表达式
package hfdobject Test35_3 {def main(args: Array[String]): Unit {println("a\tb")//定义一个规则 正则表达式//1. .表示除了换行之外的其他的任意单个字符//2. \d等于[0-9] 匹配一个数字//3. \D除了\d之外的其他的任意字符,表示非数字//4. \w等价于[…...
关于睡懒觉
我们经常听到一个词:睡懒觉。 我认为,睡懒觉这个词,是错误的。 人,是需要睡眠的,睡不够,就不会醒。睡够了,自然会醒,也不想继续睡。不信你试试,睡够了,你…...
【算法day10】栈与队列:拓展与应用
题目引用 逆波兰表达式求值滑动窗口最大值前k个高频元素 1.逆波兰表达式求值 给你一个字符串数组 tokens ,表示一个根据 逆波兰表示法 表示的算术表达式。 请你计算该表达式。返回一个表示表达式值的整数。 注意: 有效的算符为 ‘’、‘-’、‘*’ 和…...
爆肝Android JNI - 延展Android蓝牙JNI学习
零. 前言 由于Bluedroid的介绍文档有限,以及对Android的一些基本的知识需要了(Android 四大组件/AIDL/Framework/Binder机制/JNI/HIDL等),加上需要掌握的语言包括Java/C/C++等,加上网络上其实没有一个完整的介绍Bluedroid系列的文档,所以不管是蓝牙初学者还是蓝牙从业人员…...
总篇:Python3+Request+Pytest+Allure+Jenkins接口自动化框架设计思路
1、技术选型 Python3 Python 是一种广泛使用的高级编程语言,具有简洁、易读、易维护的特点。 Python 拥有丰富的第三方库,可以方便地进行接口测试的开发。 Request Request 是一个强大的 HTTP 库,用于发送 HTTP 请求和处理响应。 Request 支持多种 HTTP 方法,如 GET、P…...
Java的Map介绍以及常见方法和三种遍历方式
Java的Map介绍以及常见方法和三种遍历方式 1 Java 中的 Map 介绍 在 Java 中,Map 是一个接口,它提供了一种存储键值对(key-value pairs)的方式。每个键(key)都关联着一个值(value)…...
C/C++基础知识复习(39)
1) 什么是封装性?C中如何实现封装? 封装性(Encapsulation)是面向对象编程中的一个重要概念,它指的是将对象的状态(数据)和行为(方法)绑定在一起,并且通过访问…...
自建服务器,数据安全有保障
在远程桌面工具的选择上,向日葵和TeamViewer功能强大,但都存在收费昂贵、依赖第三方服务器、数据隐私难以完全掌控等问题。相比之下,RustDesk 凭借开源免费、自建服务的特性脱颖而出!用户可以在自己的服务器上部署RustDesk服务端&…...
CCF-GESP 编程能力认证 C++ 七级 2024年9月份判断题详细解析
链接:CCF-GESP 编程能力认证 C 七级 2024年9月份选择题详细解析-CSDN博客 目录 第 1 题 第 2 题 第 3 题 第 4 题 第 5 题 第 6 题 第 7 题 第 8 题 第 9 题 第 10 题 第 1 题 表达式 a << 1 的结果为 a(错误) 【a是字符常…...
使用Vue3+Echarts实现加载中国地图,点击省份地图下钻(完整教程)
一. 前言 在众多 ECharts 图表类型中,开发者始终绕不开的有各种各样的地图开发,关于地图开发,可能比其他图表相对繁琐一些,其实说简单也简单,说复杂也复杂,其中不乏有层级地图、3D 地图等,感觉…...
NUMA-非统一内存访问架构
NUMA(Non-Uniform Memory Access) 是一种计算机内存架构,主要用于多处理器系统。NUMA架构中的每个处理器都连接到自己的本地内存,并且可以访问其他处理器的内存,但访问其他处理器的内存速度较慢。 内核通过调度优化进…...
初识交换机和路由器
目录 初识交换机和路由器交换机路由器主要区别工作流程如果是交换机:如果是路由器 初识交换机和路由器 左为路由器,右为交换机 交换机 交换机的前身是集线器,集线器是物理层的设备,有很多接口,当一台计算机A想发消息…...
SQL面试题——滴滴SQL面试题 取出累计值与1000差值最小的记录
滴滴SQL面试题 取出累计值与1000差值最小的记录 今天的题目来自滴滴出行 已知有表cost_detail包含id和money两列,id为自增,请累加计算money值,并求出累加值与1000差值最小的记录。 +-----+--------+ | id | money | +-----+--------+ | 1 | 200 | | 2 | 300 …...
openEuler 22.03 使用cephadm安装部署ceph集群
目录 目的步骤规格步骤ceph部署前准备工作安装部署ceph集群ceph集群添加node与osdceph集群一些操作组件服务操作集群进程操作 目的 使用ceph官网的cephadm无法正常安装,会报错ERROR: Distro openeuler version 22.03 not supported 在openEuler上实现以cephadm安装部…...
C++哈希(一)
1.底层结构 顺序结构以及平衡中,元素关键码与其存储位置之间没有相对应的关系,因此在查找一个元素时,要经过关键码的多次比较。顺序查找的时间复杂度为O(N)。 理想的搜索方法:可以不经过比较,依次直接从表中直接搜索…...
OpenWrt SDK实战:如何用SDK高效开发自定义驱动和应用
OpenWrt SDK实战:如何用SDK高效开发自定义驱动和应用 在嵌入式开发领域,OpenWrt因其高度模块化和可定制性成为路由器及物联网设备的首选操作系统。但对于需要频繁修改驱动或开发定制应用的工程师来说,每次完整编译整个系统不仅耗时耗力&#…...
Analog离线引擎:从原理到实践的抗断网解决方案
Analog离线引擎:从原理到实践的抗断网解决方案 【免费下载链接】analog Meet the calendar that changes everything 项目地址: https://gitcode.com/gh_mirrors/analog4/analog 在数字化办公环境中,日程管理工具的网络依赖性常常成为效率瓶颈。远…...
如何用Tool-SQL解决Text2SQL中的条件不匹配问题?实战案例分享
实战解析:用Tool-SQL攻克Text2SQL条件不匹配难题 当数据工程师面对"帮我找出上季度华东区销售额超50万但退货率低于5%的客户"这类业务查询时,传统Text2SQL方案常陷入条件错配的泥潭——系统生成的SQL要么遗漏关键约束,要么将"…...
工业软件全景图:从核心分类到行业深度应用指南
深入理解现代制造业的核心驱动力一、 工业之魂:现代制造业的核心引擎在智能制造与工业4.0的浪潮下,工业软件已不再仅仅是辅助工具,而是被公认为“工业之魂”。它将复杂的工业知识、逻辑和经验代码化,嵌入到硬件设备和业务流程中&a…...
用 OpenClaw + 萤石云摄像头实现零成本智能看护:边缘视觉落地解法
用了一段时间 OpenClaw 之后,上周突然想到家里本来就有两个萤石云摄像头,一个在客厅看娃,一个在阳台看猫,为什么不把它们接到 OpenClaw 上。萤石云的开放平台 API 本身做得相当充分,Token 管理、云台控制、实时抓拍这些…...
[深度解析] 突破壁垒:Free-NTFS-for-Mac实现跨平台文件系统无缝协作
[深度解析] 突破壁垒:Free-NTFS-for-Mac实现跨平台文件系统无缝协作 【免费下载链接】Free-NTFS-for-Mac Nigate,一款支持苹果芯片的Free NTFS for Mac小工具软件。NTFS R/W for macOS. Support Intel/Apple Silicon now. 项目地址: https://gitcode.c…...
保姆级教程:小米AX3000T刷OpenWrt 24.10.0全流程(含救砖指南)
小米AX3000T路由器刷OpenWrt全流程实战指南 作为一名长期折腾家用路由器的技术爱好者,我最近刚完成了小米AX3000T刷OpenWrt的全过程。相比官方固件,OpenWrt提供了更强大的自定义功能和性能优化空间。本文将分享从准备工作到救砖方案的完整经验ÿ…...
Hi-C数据分析进阶:如何用dcHiC精准识别癌症样本中的区室转换事件?
Hi-C技术解密:从染色质区室动态到癌症表观遗传调控 染色质三维结构研究已成为癌症表观遗传学的前沿领域。随着Hi-C技术的普及,科学家们能够以前所未有的分辨率观察基因组在细胞核内的空间组织形式。本文将深入探讨染色质区室(A/B compartment…...
终极fabio配置验证指南:避免生产环境错误的10个实用技巧
终极fabio配置验证指南:避免生产环境错误的10个实用技巧 【免费下载链接】fabio Consul Load-Balancing made simple 项目地址: https://gitcode.com/gh_mirrors/fa/fabio fabio是一个快速、现代的零配置负载均衡HTTP(S)和TCP路由器,专为Consul管…...
STM32实战指南_基于STM32F103的智能交通灯系统设计与实现(硬件+软件+调试)
1. 项目背景与需求分析 十字路口的交通拥堵是城市治理的经典难题。传统定时切换的交通灯就像个固执的老头子,不管车多车少都按固定节奏工作,经常出现一边排长龙、另一边空荡荡的尴尬场景。这次我们要用STM32F103这颗"最强大脑"给交通灯装上&qu…...
