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

动态规划lc

先找到规律,然后找边界情况;部分特殊情况分类讨论  *递归

70.爬楼梯

简单

提示

假设你正在爬楼梯。需要 n 阶你才能到达楼顶。

每次你可以爬 1 或 2 个台阶。你有多少种不同的方法可以爬到楼顶呢?

示例 1:

输入:n = 2
输出:2
解释:有两种方法可以爬到楼顶。
1. 1 阶 + 1 阶
2. 2 阶

示例 2:

输入:n = 3
输出:3
解释:有三种方法可以爬到楼顶。
1. 1 阶 + 1 阶 + 1 阶
2. 1 阶 + 2 阶
3. 2 阶 + 1 阶

提示:

  • 1 <= n <= 45

方法一:动态规划
思路和算法

我们用 f(x) 表示爬到第 x 级台阶的方案数,考虑最后一步可能跨了一级台阶,也可能跨了两级台阶,所以我们可以列出如下式子:

f(x)=f(x−1)+f(x−2)

它意味着爬到第 x 级台阶的方案数是爬到第 x−1 级台阶的方案数和爬到第 x−2 级台阶的方案数的和。很好理解,因为每次只能爬 1 级或 2 级,所以 f(x) 只能从 f(x−1) 和 f(x−2) 转移过来,而这里要统计方案总数,我们就需要对这两项的贡献求和。

以上是动态规划的转移方程,下面我们来讨论边界条件。我们是从第 0 级开始爬的,所以从第 0 级爬到第 0 级我们可以看作只有一种方案,即 f(0)=1;从第 0 级到第 1 级也只有一种方案,即爬一级,f(1)=1。这两个作为边界条件就可以继续向后推导出第 n 级的正确结果。我们不妨写几项来验证一下,根据转移方程得到 f(2)=2,f(3)=3,f(4)=5,……,我们把这些情况都枚举出来,发现计算的结果是正确的。

我们不难通过转移方程和边界条件给出一个时间复杂度和空间复杂度都是 O(n) 的实现,但是由于这里的 f(x) 只和 f(x−1) 与 f(x−2) 有关,所以我们可以用「滚动数组思想」把空间复杂度优化成 O(1)。下面的代码中给出的就是这种实现。

509. 斐波那契数

尝试过

简单

相关标签

相关企业

斐波那契数 (通常用 F(n) 表示)形成的序列称为 斐波那契数列 。该数列由 0 和 1 开始,后面的每一项数字都是前面两项数字的和。也就是:

F(0) = 0,F(1) = 1
F(n) = F(n - 1) + F(n - 2),其中 n > 1

给定 n ,请计算 F(n) 。

这个就是只有第三个才开始变成斐波那契,所以应该分类讨论

class Solution {public int fib(int n) {if(n<2){return n;}int p=0;int q=0;int r=1;for (int i=2;i<=n;i++){p=q;q=r;r=p+q;}return r;}
}

1137. 第 N 个泰波那契数

泰波那契序列 Tn 定义如下: 

T0 = 0, T1 = 1, T2 = 1, 且在 n >= 0 的条件下 Tn+3 = Tn + Tn+1 + Tn+2

给你整数 n,请返回第 n 个泰波那契数 Tn 的值。

示例 1:

输入:n = 4
输出:4
解释:
T_3 = 0 + 1 + 1 = 2
T_4 = 1 + 1 + 2 = 4
class Solution {public int tribonacci(int n) {if (n==0){return 0;}if (n<=2){return 1;}int i=0,j=0,k=1,r=1;//每次设定的时候,保留一次for循环里的滚动一次,即多一位0(其实i是任意数字都没关系)for (int m=3;m<=n;m++){//记得从第几个tri开始i=j;j=k;k=r;r=i+j+k;}return r;}
}

相关文章:

动态规划lc

先找到规律&#xff0c;然后找边界情况&#xff1b;部分特殊情况分类讨论 *递归 70.爬楼梯 简单 提示 假设你正在爬楼梯。需要 n 阶你才能到达楼顶。 每次你可以爬 1 或 2 个台阶。你有多少种不同的方法可以爬到楼顶呢&#xff1f; 示例 1&#xff1a; 输入&#xff1a…...

介绍xshell的使用技巧

使用技巧目录 1. 开启左键选中即复制&#xff0c;右键点击即粘贴2. 开启撰写功能3. 开启日志记录功能 1. 开启左键选中即复制&#xff0c;右键点击即粘贴 参考&#xff1a;https://blog.csdn.net/chirrupy_hamal/article/details/108619262 2. 开启撰写功能 使用场景&#x…...

揭秘语音识别巨头1:国内外顶尖技术服务商全解析01(万字长文)

一、学习导航 解密语音识别巨头&#xff1a;国内顶尖技术服务商全解析00&#xff1a;学习地图 解密语音识别巨头&#xff1a;国内顶尖技术服务商全解析01&#xff1a;微软语音&#xff0c;商业No.1 解密语音识别巨头&#xff1a;国内顶尖技术服务商全解析02&#xff1a;百度…...

JAVA使用SM2算法生成密钥对加密解密加签验签

简介 SM2是非对称加密算法&#xff0c;一提非对称加密算法&#xff0c;第一想到的是RSA&#xff0c;没错&#xff0c;这个就是替代RSA的。它是基于椭圆曲线密码的公钥密码算法标准&#xff0c;其秘钥长度256bit&#xff0c;包含数字签名、密钥交换和公钥加密&#xff0c;用于替…...

uniapp(vue)打包web项目页面刷新后报404解决方案

一、问题概述 uniapp是一款优秀的跨平台开发框架&#xff0c;它可以帮助开发者快速构建出适用于多端的应用程序。然而&#xff0c;在项目打包后&#xff0c;有可能发现页面在刷新时会出现404错误。这无疑给用户体验带来了极大的困扰&#xff0c;下面我们就来分析一下这个问题。…...

ansible学习之ansible-vault

相关文档参考:http://www.ansible.com.cn/docs/playbooks_vault.html#what-can-be-encrypted-with-vault ansible-vault 功能介绍 Ansible-Vault是一个用于加密和管理Ansible playbook中敏感数据的工具。通过创建、编辑、加密、解密、查看和重置密码&#xff0c;可以安全地存储…...

封装el-upload组件,用于上传图片和视频的组件

使用环境 vue3element plus 需要根据后端返回结构修改的函数&#xff1a;onPreview onRemove onSuccess 组件使用 基本使用 源代码&#xff1a; <script setup> import AutoUploadFile from /components/auto-upload-file/index.vue function change(urls){console.log…...

6.将扩散模型与其他生成模型的关联(2)

1.归一化流与扩散模型 自一化流(Normalizing Flow)是生成模型&#xff0c;通过将易于处理的分布进行变换以队对高维数据进行建模。归一化流可以将简单的概率分布转化为极其复杂的分布&#xff0c;并用于强化学习、变分推理等领域。 现有的归一化流是基于变量替换公式构…...

【C++】基于红黑树封装set和map

&#x1f680;个人主页&#xff1a;小羊 &#x1f680;所属专栏&#xff1a;C 很荣幸您能阅读我的文章&#xff0c;诚请评论指点&#xff0c;欢迎欢迎 ~ 目录 前言一、更高维度的泛型二、模版参数三、比较逻辑的重写四、迭代器4.1 const迭代器4.2 重载4.3 - -重载 五、完整代…...

24最新新手入门指南:Stable Diffusion!

前言 Stable Diffusion&#xff0c;一款新兴的开源AI绘画软件&#xff0c;正逐渐成为数字艺术家和爱好者的新宠。它的强大功能让用户能够轻松创造出令人印象深刻的数字艺术作品。 无论你是专业艺术家还是艺术新手&#xff0c;Stable Diffusion都为你提供了一个探索创造力的新…...

Java-基础

1. 导入模块不能纯粹的复制粘贴&#xff0c;要从new里导入&#xff0c;因为前者建立不了关联 2. 数组 String[] name{"张三","李四","王五"};int[] numsnew int[]{1,2,3};//二维String[][] names{{"张三","李四"},{"…...

二、后台管理系统布局菜单可拖动

前两天产品提出了一个需求,说后台管理系统的左边菜单的名称字数过多,遮挡了。希望能让客户能够看到全部的名称,给左侧菜单增加一个可拖动的功能,经过我的研究,这个功能最终也做出来了,先看效果,双击查看。 下面咱们进入实现步骤 第一步,找到文件。一般的项目中都存在l…...

socket和http区别

socket和http区别&#xff1a;1、主体不同&#xff1b;2、所处层次不同&#xff1b;3、连接状态不同&#xff1b;4、传输数据量不同&#xff1b;5、数据安全性不同&#xff1b;6、连接方式不同。其中&#xff0c;主体不同指的是socke是一个调用接口&#xff08;API&#xff09;…...

算法:974.和可以被K整除的子数组

题目 链接:leetcode链接 思路分析&#xff08;前缀和 同余定理&#xff09; 首先&#xff0c;我们要了解一下什么是同余定理 同余定理&#xff1a; 如果&#xff08;a - b&#xff09;/ p k …… 0 则 a % p b % p 证明我写在草稿纸上&#xff0c;如下图&#xff1a; 初…...

QD1-P8 HTML 格式化标签(font、pre、b、strong、i、u、del、s、sub、sup)

本节学习&#xff1a;HTML 格式化标签。 本节视频 www.bilibili.com/video/BV1n64y1U7oj?p8 ‍ 一、font 标签 用途&#xff1a;定义文本的字体大小、颜色和 face&#xff08;字体类型&#xff09;。 示例 <!DOCTYPE html> <html><head><meta cha…...

红米Turbo 3工程固件预览 修复底层 体验原生态系统 默认开启diag端口

红米Turbo 3机型代码:peridot 国外版本:POCO F6 用于以下型号的小米机型:24069RA21C, 24069PC21G, 24069PC21I。搭载1.5K OLED屏、骁龙8s处理器、5000mAh电池+90W快充、5000万像素主摄。 通过博文了解 1💝💝💝-----此机型工程固件的资源刷写注意事项 2💝💝�…...

sql的调优指南及高级sql技巧

SQL调优是优化数据库性能的重要手段&#xff0c;涉及编写高效的SQL查询、合理设计索引、优化数据库结构等。以下是一些SQL调优指南和高级技巧&#xff1a; SQL调优指南 选择合适的查询方式&#xff1a; **避免使用SELECT ***&#xff1a;仅选择所需的列&#xff0c;减少数据传…...

生成式专题的第一节课---GAN图像生成

一、GAN的起源与发展 1.GAN的起源 GAN &#xff08;生成式对抗网络&#xff09;诞生于 2014 年&#xff0c;由 Ian Goodfellow 提出&#xff0c;是用于生成数据的深度学习模型&#xff0c;创新点是对抗性训练&#xff0c;即生成器与判别器的竞争关系&#xff0c;为图像生成、…...

中科星图GVE(案例)——AI实现建筑用地变化前后对比情况

目录 简介 函数 gve.Services.AI.ConstructionLandChangeExtraction(image1,image2) 代码 结果 知识星球 机器学习 简介 AI可以通过分析卫星图像、航拍影像或其他地理信息数据&#xff0c;实现建筑用地变化前后对比。以下是一种可能的实现方法&#xff1a; 数据获取&am…...

Spring Boot中获取application.yml中属性的几种方式

在Spring Boot应用程序中&#xff0c;可以通过多种方式从application.yml文件中获取配置属性。以下是几种常见的方法&#xff1a; 1. 使用Value注解 你可以使用Value注解将application.yml中的属性注入到Spring管理的bean中。 application.yml app:name: MySpringBootAppve…...

JavaSec-RCE

简介 RCE(Remote Code Execution)&#xff0c;可以分为:命令注入(Command Injection)、代码注入(Code Injection) 代码注入 1.漏洞场景&#xff1a;Groovy代码注入 Groovy是一种基于JVM的动态语言&#xff0c;语法简洁&#xff0c;支持闭包、动态类型和Java互操作性&#xff0c…...

地震勘探——干扰波识别、井中地震时距曲线特点

目录 干扰波识别反射波地震勘探的干扰波 井中地震时距曲线特点 干扰波识别 有效波&#xff1a;可以用来解决所提出的地质任务的波&#xff1b;干扰波&#xff1a;所有妨碍辨认、追踪有效波的其他波。 地震勘探中&#xff0c;有效波和干扰波是相对的。例如&#xff0c;在反射波…...

<6>-MySQL表的增删查改

目录 一&#xff0c;create&#xff08;创建表&#xff09; 二&#xff0c;retrieve&#xff08;查询表&#xff09; 1&#xff0c;select列 2&#xff0c;where条件 三&#xff0c;update&#xff08;更新表&#xff09; 四&#xff0c;delete&#xff08;删除表&#xf…...

K8S认证|CKS题库+答案| 11. AppArmor

目录 11. AppArmor 免费获取并激活 CKA_v1.31_模拟系统 题目 开始操作&#xff1a; 1&#xff09;、切换集群 2&#xff09;、切换节点 3&#xff09;、切换到 apparmor 的目录 4&#xff09;、执行 apparmor 策略模块 5&#xff09;、修改 pod 文件 6&#xff09;、…...

渗透实战PortSwigger靶场-XSS Lab 14:大多数标签和属性被阻止

<script>标签被拦截 我们需要把全部可用的 tag 和 event 进行暴力破解 XSS cheat sheet&#xff1a; https://portswigger.net/web-security/cross-site-scripting/cheat-sheet 通过爆破发现body可以用 再把全部 events 放进去爆破 这些 event 全部可用 <body onres…...

UDP(Echoserver)

网络命令 Ping 命令 检测网络是否连通 使用方法: ping -c 次数 网址ping -c 3 www.baidu.comnetstat 命令 netstat 是一个用来查看网络状态的重要工具. 语法&#xff1a;netstat [选项] 功能&#xff1a;查看网络状态 常用选项&#xff1a; n 拒绝显示别名&#…...

P3 QT项目----记事本(3.8)

3.8 记事本项目总结 项目源码 1.main.cpp #include "widget.h" #include <QApplication> int main(int argc, char *argv[]) {QApplication a(argc, argv);Widget w;w.show();return a.exec(); } 2.widget.cpp #include "widget.h" #include &q…...

在鸿蒙HarmonyOS 5中使用DevEco Studio实现录音机应用

1. 项目配置与权限设置 1.1 配置module.json5 {"module": {"requestPermissions": [{"name": "ohos.permission.MICROPHONE","reason": "录音需要麦克风权限"},{"name": "ohos.permission.WRITE…...

OPenCV CUDA模块图像处理-----对图像执行 均值漂移滤波(Mean Shift Filtering)函数meanShiftFiltering()

操作系统&#xff1a;ubuntu22.04 OpenCV版本&#xff1a;OpenCV4.9 IDE:Visual Studio Code 编程语言&#xff1a;C11 算法描述 在 GPU 上对图像执行 均值漂移滤波&#xff08;Mean Shift Filtering&#xff09;&#xff0c;用于图像分割或平滑处理。 该函数将输入图像中的…...

算法笔记2

1.字符串拼接最好用StringBuilder&#xff0c;不用String 2.创建List<>类型的数组并创建内存 List arr[] new ArrayList[26]; Arrays.setAll(arr, i -> new ArrayList<>()); 3.去掉首尾空格...