动态规划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
先找到规律,然后找边界情况;部分特殊情况分类讨论 *递归 70.爬楼梯 简单 提示 假设你正在爬楼梯。需要 n 阶你才能到达楼顶。 每次你可以爬 1 或 2 个台阶。你有多少种不同的方法可以爬到楼顶呢? 示例 1: 输入:…...

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

揭秘语音识别巨头1:国内外顶尖技术服务商全解析01(万字长文)
一、学习导航 解密语音识别巨头:国内顶尖技术服务商全解析00:学习地图 解密语音识别巨头:国内顶尖技术服务商全解析01:微软语音,商业No.1 解密语音识别巨头:国内顶尖技术服务商全解析02:百度…...
JAVA使用SM2算法生成密钥对加密解密加签验签
简介 SM2是非对称加密算法,一提非对称加密算法,第一想到的是RSA,没错,这个就是替代RSA的。它是基于椭圆曲线密码的公钥密码算法标准,其秘钥长度256bit,包含数字签名、密钥交换和公钥加密,用于替…...
uniapp(vue)打包web项目页面刷新后报404解决方案
一、问题概述 uniapp是一款优秀的跨平台开发框架,它可以帮助开发者快速构建出适用于多端的应用程序。然而,在项目打包后,有可能发现页面在刷新时会出现404错误。这无疑给用户体验带来了极大的困扰,下面我们就来分析一下这个问题。…...
ansible学习之ansible-vault
相关文档参考:http://www.ansible.com.cn/docs/playbooks_vault.html#what-can-be-encrypted-with-vault ansible-vault 功能介绍 Ansible-Vault是一个用于加密和管理Ansible playbook中敏感数据的工具。通过创建、编辑、加密、解密、查看和重置密码,可以安全地存储…...

封装el-upload组件,用于上传图片和视频的组件
使用环境 vue3element plus 需要根据后端返回结构修改的函数:onPreview onRemove onSuccess 组件使用 基本使用 源代码: <script setup> import AutoUploadFile from /components/auto-upload-file/index.vue function change(urls){console.log…...
6.将扩散模型与其他生成模型的关联(2)
1.归一化流与扩散模型 自一化流(Normalizing Flow)是生成模型,通过将易于处理的分布进行变换以队对高维数据进行建模。归一化流可以将简单的概率分布转化为极其复杂的分布,并用于强化学习、变分推理等领域。 现有的归一化流是基于变量替换公式构…...

【C++】基于红黑树封装set和map
🚀个人主页:小羊 🚀所属专栏:C 很荣幸您能阅读我的文章,诚请评论指点,欢迎欢迎 ~ 目录 前言一、更高维度的泛型二、模版参数三、比较逻辑的重写四、迭代器4.1 const迭代器4.2 重载4.3 - -重载 五、完整代…...

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

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

二、后台管理系统布局菜单可拖动
前两天产品提出了一个需求,说后台管理系统的左边菜单的名称字数过多,遮挡了。希望能让客户能够看到全部的名称,给左侧菜单增加一个可拖动的功能,经过我的研究,这个功能最终也做出来了,先看效果,双击查看。 下面咱们进入实现步骤 第一步,找到文件。一般的项目中都存在l…...
socket和http区别
socket和http区别:1、主体不同;2、所处层次不同;3、连接状态不同;4、传输数据量不同;5、数据安全性不同;6、连接方式不同。其中,主体不同指的是socke是一个调用接口(API)…...

算法:974.和可以被K整除的子数组
题目 链接:leetcode链接 思路分析(前缀和 同余定理) 首先,我们要了解一下什么是同余定理 同余定理: 如果(a - b)/ p k …… 0 则 a % p b % p 证明我写在草稿纸上,如下图: 初…...

QD1-P8 HTML 格式化标签(font、pre、b、strong、i、u、del、s、sub、sup)
本节学习:HTML 格式化标签。 本节视频 www.bilibili.com/video/BV1n64y1U7oj?p8 一、font 标签 用途:定义文本的字体大小、颜色和 face(字体类型)。 示例 <!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调优是优化数据库性能的重要手段,涉及编写高效的SQL查询、合理设计索引、优化数据库结构等。以下是一些SQL调优指南和高级技巧: SQL调优指南 选择合适的查询方式: **避免使用SELECT ***:仅选择所需的列,减少数据传…...

生成式专题的第一节课---GAN图像生成
一、GAN的起源与发展 1.GAN的起源 GAN (生成式对抗网络)诞生于 2014 年,由 Ian Goodfellow 提出,是用于生成数据的深度学习模型,创新点是对抗性训练,即生成器与判别器的竞争关系,为图像生成、…...

中科星图GVE(案例)——AI实现建筑用地变化前后对比情况
目录 简介 函数 gve.Services.AI.ConstructionLandChangeExtraction(image1,image2) 代码 结果 知识星球 机器学习 简介 AI可以通过分析卫星图像、航拍影像或其他地理信息数据,实现建筑用地变化前后对比。以下是一种可能的实现方法: 数据获取&am…...
Spring Boot中获取application.yml中属性的几种方式
在Spring Boot应用程序中,可以通过多种方式从application.yml文件中获取配置属性。以下是几种常见的方法: 1. 使用Value注解 你可以使用Value注解将application.yml中的属性注入到Spring管理的bean中。 application.yml app:name: MySpringBootAppve…...
Vue记事本应用实现教程
文章目录 1. 项目介绍2. 开发环境准备3. 设计应用界面4. 创建Vue实例和数据模型5. 实现记事本功能5.1 添加新记事项5.2 删除记事项5.3 清空所有记事 6. 添加样式7. 功能扩展:显示创建时间8. 功能扩展:记事项搜索9. 完整代码10. Vue知识点解析10.1 数据绑…...
【杂谈】-递归进化:人工智能的自我改进与监管挑战
递归进化:人工智能的自我改进与监管挑战 文章目录 递归进化:人工智能的自我改进与监管挑战1、自我改进型人工智能的崛起2、人工智能如何挑战人类监管?3、确保人工智能受控的策略4、人类在人工智能发展中的角色5、平衡自主性与控制力6、总结与…...
前端倒计时误差!
提示:记录工作中遇到的需求及解决办法 文章目录 前言一、误差从何而来?二、五大解决方案1. 动态校准法(基础版)2. Web Worker 计时3. 服务器时间同步4. Performance API 高精度计时5. 页面可见性API优化三、生产环境最佳实践四、终极解决方案架构前言 前几天听说公司某个项…...
基于服务器使用 apt 安装、配置 Nginx
🧾 一、查看可安装的 Nginx 版本 首先,你可以运行以下命令查看可用版本: apt-cache madison nginx-core输出示例: nginx-core | 1.18.0-6ubuntu14.6 | http://archive.ubuntu.com/ubuntu focal-updates/main amd64 Packages ng…...
uniapp中使用aixos 报错
问题: 在uniapp中使用aixos,运行后报如下错误: AxiosError: There is no suitable adapter to dispatch the request since : - adapter xhr is not supported by the environment - adapter http is not available in the build 解决方案&…...

多种风格导航菜单 HTML 实现(附源码)
下面我将为您展示 6 种不同风格的导航菜单实现,每种都包含完整 HTML、CSS 和 JavaScript 代码。 1. 简约水平导航栏 <!DOCTYPE html> <html lang"zh-CN"> <head><meta charset"UTF-8"><meta name"viewport&qu…...

回溯算法学习
一、电话号码的字母组合 import java.util.ArrayList; import java.util.List;import javax.management.loading.PrivateClassLoader;public class letterCombinations {private static final String[] KEYPAD {"", //0"", //1"abc", //2"…...
CSS | transition 和 transform的用处和区别
省流总结: transform用于变换/变形,transition是动画控制器 transform 用来对元素进行变形,常见的操作如下,它是立即生效的样式变形属性。 旋转 rotate(角度deg)、平移 translateX(像素px)、缩放 scale(倍数)、倾斜 skewX(角度…...

脑机新手指南(七):OpenBCI_GUI:从环境搭建到数据可视化(上)
一、OpenBCI_GUI 项目概述 (一)项目背景与目标 OpenBCI 是一个开源的脑电信号采集硬件平台,其配套的 OpenBCI_GUI 则是专为该硬件设计的图形化界面工具。对于研究人员、开发者和学生而言,首次接触 OpenBCI 设备时,往…...

手机平板能效生态设计指令EU 2023/1670标准解读
手机平板能效生态设计指令EU 2023/1670标准解读 以下是针对欧盟《手机和平板电脑生态设计法规》(EU) 2023/1670 的核心解读,综合法规核心要求、最新修正及企业合规要点: 一、法规背景与目标 生效与强制时间 发布于2023年8月31日(OJ公报&…...