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

牛客网 DP3跳台阶扩展问题

在原始跳台阶问题上,我们知道只走1,2阶台阶的话,可以推出来斐波那契数列的形式进行计算操作。但是,在这里就是1,2,3,...n阶台阶了。其实思路是一样的。

在原始台阶问题,我们的状态方程是:f(n)=f(n-1)+f(n-2)的,这里解释为选择走一阶台阶,那么剩下有f(n-1)种走法,走2阶台阶,有f(n-2)种走法;同理,走3阶台阶,剩下f(n-3)种走法......

以此类推之后,我们得出了:f(n)=f(n-1)+f(n-2)+f(n-3)+...+f(1)+f(0).的状态方程,这样我们就可以解出来了。

注意:其实状态方程列出来之后,是一个递归的过程,我们需要知道这是怎么计算出来的,那么,n=0,1时都是一种解法,n=2时就是2种解法了,而到了n=3的时候就是f(3)=f(2)+f(1)+f(0)了,这个时候f(3)就是4了。以此类推我们可以发现,f(n)=2^(n-1),这样我们就可以放心递归了,或者你直接用这个式子计算返回值就行。

上代码:

#include <iostream>
#include<cmath>
#define MAX 100
using namespace std;
typedef long long LL;LL sum(int n){if(n==0)return 1;else if(n==1)return 1;else if(n==2)return 2;elsereturn 2*sum(n-1);}
int main() {int n;cin>>n;cout<<sum(n)<<endl;
}

相关文章:

牛客网 DP3跳台阶扩展问题

在原始跳台阶问题上&#xff0c;我们知道只走1&#xff0c;2阶台阶的话&#xff0c;可以推出来斐波那契数列的形式进行计算操作。但是&#xff0c;在这里就是1&#xff0c;2&#xff0c;3&#xff0c;...n阶台阶了。其实思路是一样的。 在原始台阶问题&#xff0c;我们的状态方…...

ARM汇编[1] 打印格式化字符串(printf

文章目录 写在前面关键知识简单加减乘除函数调用和循环系统调用栈的使用 GDB调试示例代码 写在前面 如果您对ARM汇编还一无所知的话请先参考ARM汇编hello world 本篇不会广泛详细的列举各种指令&#xff0c;仍然只讲解最关键的部分&#xff0c;然后使用他们来完成一个汇编程序…...

Java 集合、迭代器

Java 集合框架主要包括两种类型的容器&#xff0c;一种是集合&#xff08;Collection&#xff09;&#xff0c;存储一个元素集合&#xff0c;另一种是图&#xff08;Map&#xff09;&#xff0c;存储键/值对映射。Collection 接口又有 3 种子类型&#xff0c;List、Set 和 Queu…...

在 Docker 中启动 ROS2 里的 rivz2 和 rqt 出现错误的解决方法

1. 出现错误&#xff1a; 运行 ros2 run rivz2 rivz2 &#xff0c;报错如下 &#xff1a; No protocol specified qt.qpa.xcb: could not connect to display :1 qt.qpa.plugin: Could not load the Qt platform plugin "xcb" in "" even though it was f…...

使用securecrt+xming通过x11访问ubuntu可视化程序

windows使用securecrtxming通过x11访问ubuntu可视化程序 windows机器IP&#xff1a;192.168.9.133 ubuntu-desktop20.04机器IP&#xff1a;192.168.9.190 windows下载xming并安装 按照图修改xming配置 开始->xming->Xlaunch 完成xming会在右下角后台运行 windows在…...

红队打靶练习:HEALTHCARE: 1

目录 信息收集 1、arp 2、nmap 3、nikto 4、whatweb 目录探测 1、gobuster 2、dirsearch WEB web信息收集 gobuster cms sqlmap 爆库 爆表 爆列 爆字段 FTP 提权 信息收集 本地提权 信息收集 1、arp ┌──(root㉿ru)-[~/kali] └─# arp-scan -l Inte…...

Java IO:概念和分类总结

前言 大家好&#xff0c;我是chowley&#xff0c;刚看完Java IO方面内容&#xff0c;特此总结一下。 Java IO Java IO&#xff08;输入输出&#xff09;是Java编程中用于处理输入和输出的API。它提供了一套丰富的类和方法&#xff0c;用于读取和写入数据到不同的设备、文件和…...

【Linux】基本命令(下)

目录 head指令 && tail指令 head指令 tail指令 find指令 grep指令 zip/unzip指令 tar指令 时间相关的指令 date显示 1.在显示方面&#xff0c;使用者可以设定欲显示的格式&#xff0c;格式设定为一个加号后接数个标记&#xff0c;其中常用的标记列表如下&…...

腾讯云游戏联机服务器配置价格表,4核16G/8核32G/4核32G/16核64G

2024年更新腾讯云游戏联机服务器配置价格表&#xff0c;可用于搭建幻兽帕鲁、雾锁王国等游戏服务器&#xff0c;游戏服务器配置可选4核16G12M、8核32G22M、4核32G10M、16核64G35M、4核16G14M等配置&#xff0c;可以选择轻量应用服务器和云服务器CVM内存型MA3或标准型SA2实例&am…...

面试经典150题——长度最小的子数组

​"In the midst of winter, I found there was, within me, an invincible summer." - Albert Camus 1. 题目描述 2. 题目分析与解析 首先理解题意&#xff0c;题目要求我们找到一个长度最小的 连续子数组 满足他们的和大于target&#xff0c;需要返回的是子数组的…...

业务流程

一、需求分析和设计&#xff1a; 在项目启动阶段&#xff0c;需要与业务人员和产品经理充分沟通&#xff0c;了解业务需求&#xff0c;并根据需求进行系统设计和数据库设计。这一阶段的输出通常是需求文档、系统架构设计、数据库设计等。 1.需求文档 需求文档是一份非常重要…...

ChatGPT Plus如何升级?信用卡付款失败怎么办?如何使用信用卡升级 ChatGPT Plus?

ChatGPT Plus是OpenAI提供的一种高级服务&#xff0c;它相较于标准版本&#xff0c;提供了更快的响应速度、更强大的功能&#xff0c;并且用户可以优先体验到新推出的功能。 尽管许多用户愿意支付 20 美元的月费来订阅 GPT-4&#xff0c;但在实际支付过程中&#xff0c;特别是…...

Spring 如何配置 bean (XML 方式)

请直接看原文:Spring 如何配置 bean (XML 方式)_spring 在哪配置bean 文件-CSDN博客 -------------------------------------------------------------------------------------------------------------------------------- Java Bean 如何配置配置到 spring 容器中 基于 XM…...

揭秘外观模式:简化复杂系统的关键设计策略

前言 外观模式&#xff08;Facade Pattern&#xff09;是一种结构型设计模式&#xff0c;它隐藏了系统的复杂性&#xff0c;并向客户端提供了一个可以访问系统的接口。这种类型的设计模式向现有的系统添加一个接口&#xff0c;来隐藏系统的复杂性。这种模式涉及到一个单一的类…...

Nginx 命令(Ubuntu)

常用命令&#xff1a; 1.查看错误日志&#xff1a; sudo vim /var/log/nginx/error.log 2.重新加载 nignx sudo systemctl reload nginx 3.立即停止Nginx服务。如果Nginx正在运行&#xff0c;它将被终止 sudo systemctl stop nginx 4. 禁止Nginx服务在系统重启时自动启…...

从github上拉取项目到pycharm中

有两种方法&#xff0c;方法一较为简单&#xff0c;方法二用到了git bash&#xff0c;推荐方法一 目录 有两种方法&#xff0c;方法一较为简单&#xff0c;方法二用到了git bash&#xff0c;推荐方法一方法一&#xff1a;方法二&#xff1a; 方法一&#xff1a; 在github上复制…...

python从入门到精通(十八):python爬虫的练习案列集合

python爬虫的练习 1.爬取天气网的北京城市历史天气数据1.1 第一种使用面向对象OOP编写爬虫1.2 第二种使用面向过程函数编写爬虫 1.爬取天气网的北京城市历史天气数据 1.1 第一种使用面向对象OOP编写爬虫 import re import requests from bs4 import BeautifulSoup import xlw…...

2.12作业

第一题&#xff1a;段错误。 第二题&#xff1a;hello world 第三题&#xff1a;hello 第四题&#xff1a;world 第五题&#xff1a; a: int a; b: int*a; c: int a0;int *p&a;int **q&p; d: int a[10]; e: int *a[10]; …...

树莓派4B(Raspberry Pi 4B) 使用docker搭建单机版nacos

树莓派4B&#xff08;Raspberry Pi 4B&#xff09; 使用docker搭建单机版nacos ⚠️ 由于树莓派上的芯片是ARM架构&#xff0c;而官方推出的docker镜像不适用于ARM架构&#xff0c;所以想用树莓派搭建最新版的Nacos服务的小伙伴们可以忽略我这篇文章了。本文基于nacos 2.0.4&am…...

C++入门学习(二十七)跳转语句—continue语句

当在循环中遇到continue语句时&#xff0c;它会跳过当前迭代剩余的代码块&#xff0c;并立即开始下一次迭代。这意味着continue语句用于跳过循环中特定的执行步骤&#xff0c;而不是完全终止循环。 直接看一下下面的代码更清晰&#xff1a; 与上一节的break语句可以做一下对比…...

超短脉冲激光自聚焦效应

前言与目录 强激光引起自聚焦效应机理 超短脉冲激光在脆性材料内部加工时引起的自聚焦效应&#xff0c;这是一种非线性光学现象&#xff0c;主要涉及光学克尔效应和材料的非线性光学特性。 自聚焦效应可以产生局部的强光场&#xff0c;对材料产生非线性响应&#xff0c;可能…...

论文解读:交大港大上海AI Lab开源论文 | 宇树机器人多姿态起立控制强化学习框架(二)

HoST框架核心实现方法详解 - 论文深度解读(第二部分) 《Learning Humanoid Standing-up Control across Diverse Postures》 系列文章: 论文深度解读 + 算法与代码分析(二) 作者机构: 上海AI Lab, 上海交通大学, 香港大学, 浙江大学, 香港中文大学 论文主题: 人形机器人…...

CMake基础:构建流程详解

目录 1.CMake构建过程的基本流程 2.CMake构建的具体步骤 2.1.创建构建目录 2.2.使用 CMake 生成构建文件 2.3.编译和构建 2.4.清理构建文件 2.5.重新配置和构建 3.跨平台构建示例 4.工具链与交叉编译 5.CMake构建后的项目结构解析 5.1.CMake构建后的目录结构 5.2.构…...

【大模型RAG】Docker 一键部署 Milvus 完整攻略

本文概要 Milvus 2.5 Stand-alone 版可通过 Docker 在几分钟内完成安装&#xff1b;只需暴露 19530&#xff08;gRPC&#xff09;与 9091&#xff08;HTTP/WebUI&#xff09;两个端口&#xff0c;即可让本地电脑通过 PyMilvus 或浏览器访问远程 Linux 服务器上的 Milvus。下面…...

深入解析C++中的extern关键字:跨文件共享变量与函数的终极指南

&#x1f680; C extern 关键字深度解析&#xff1a;跨文件编程的终极指南 &#x1f4c5; 更新时间&#xff1a;2025年6月5日 &#x1f3f7;️ 标签&#xff1a;C | extern关键字 | 多文件编程 | 链接与声明 | 现代C 文章目录 前言&#x1f525;一、extern 是什么&#xff1f;&…...

springboot整合VUE之在线教育管理系统简介

可以学习到的技能 学会常用技术栈的使用 独立开发项目 学会前端的开发流程 学会后端的开发流程 学会数据库的设计 学会前后端接口调用方式 学会多模块之间的关联 学会数据的处理 适用人群 在校学生&#xff0c;小白用户&#xff0c;想学习知识的 有点基础&#xff0c;想要通过项…...

打手机检测算法AI智能分析网关V4守护公共/工业/医疗等多场景安全应用

一、方案背景​ 在现代生产与生活场景中&#xff0c;如工厂高危作业区、医院手术室、公共场景等&#xff0c;人员违规打手机的行为潜藏着巨大风险。传统依靠人工巡查的监管方式&#xff0c;存在效率低、覆盖面不足、判断主观性强等问题&#xff0c;难以满足对人员打手机行为精…...

[ACTF2020 新生赛]Include 1(php://filter伪协议)

题目 做法 启动靶机&#xff0c;点进去 点进去 查看URL&#xff0c;有 ?fileflag.php说明存在文件包含&#xff0c;原理是php://filter 协议 当它与包含函数结合时&#xff0c;php://filter流会被当作php文件执行。 用php://filter加编码&#xff0c;能让PHP把文件内容…...

Linux系统部署KES

1、安装准备 1.版本说明V008R006C009B0014 V008&#xff1a;是version产品的大版本。 R006&#xff1a;是release产品特性版本。 C009&#xff1a;是通用版 B0014&#xff1a;是build开发过程中的构建版本2.硬件要求 #安全版和企业版 内存&#xff1a;1GB 以上 硬盘&#xf…...

Docker拉取MySQL后数据库连接失败的解决方案

在使用Docker部署MySQL时&#xff0c;拉取并启动容器后&#xff0c;有时可能会遇到数据库连接失败的问题。这种问题可能由多种原因导致&#xff0c;包括配置错误、网络设置问题、权限问题等。本文将分析可能的原因&#xff0c;并提供解决方案。 一、确认MySQL容器的运行状态 …...