当前位置: 首页 > 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语句可以做一下对比…...

第19节 Node.js Express 框架

Express 是一个为Node.js设计的web开发框架&#xff0c;它基于nodejs平台。 Express 简介 Express是一个简洁而灵活的node.js Web应用框架, 提供了一系列强大特性帮助你创建各种Web应用&#xff0c;和丰富的HTTP工具。 使用Express可以快速地搭建一个完整功能的网站。 Expre…...

测试微信模版消息推送

进入“开发接口管理”--“公众平台测试账号”&#xff0c;无需申请公众账号、可在测试账号中体验并测试微信公众平台所有高级接口。 获取access_token: 自定义模版消息&#xff1a; 关注测试号&#xff1a;扫二维码关注测试号。 发送模版消息&#xff1a; import requests da…...

Cursor实现用excel数据填充word模版的方法

cursor主页&#xff1a;https://www.cursor.com/ 任务目标&#xff1a;把excel格式的数据里的单元格&#xff0c;按照某一个固定模版填充到word中 文章目录 注意事项逐步生成程序1. 确定格式2. 调试程序 注意事项 直接给一个excel文件和最终呈现的word文件的示例&#xff0c;…...

Spark 之 入门讲解详细版(1)

1、简介 1.1 Spark简介 Spark是加州大学伯克利分校AMP实验室&#xff08;Algorithms, Machines, and People Lab&#xff09;开发通用内存并行计算框架。Spark在2013年6月进入Apache成为孵化项目&#xff0c;8个月后成为Apache顶级项目&#xff0c;速度之快足见过人之处&…...

React Native 开发环境搭建(全平台详解)

React Native 开发环境搭建&#xff08;全平台详解&#xff09; 在开始使用 React Native 开发移动应用之前&#xff0c;正确设置开发环境是至关重要的一步。本文将为你提供一份全面的指南&#xff0c;涵盖 macOS 和 Windows 平台的配置步骤&#xff0c;如何在 Android 和 iOS…...

Admin.Net中的消息通信SignalR解释

定义集线器接口 IOnlineUserHub public interface IOnlineUserHub {/// 在线用户列表Task OnlineUserList(OnlineUserList context);/// 强制下线Task ForceOffline(object context);/// 发布站内消息Task PublicNotice(SysNotice context);/// 接收消息Task ReceiveMessage(…...

PPT|230页| 制造集团企业供应链端到端的数字化解决方案:从需求到结算的全链路业务闭环构建

制造业采购供应链管理是企业运营的核心环节&#xff0c;供应链协同管理在供应链上下游企业之间建立紧密的合作关系&#xff0c;通过信息共享、资源整合、业务协同等方式&#xff0c;实现供应链的全面管理和优化&#xff0c;提高供应链的效率和透明度&#xff0c;降低供应链的成…...

java调用dll出现unsatisfiedLinkError以及JNA和JNI的区别

UnsatisfiedLinkError 在对接硬件设备中&#xff0c;我们会遇到使用 java 调用 dll文件 的情况&#xff0c;此时大概率出现UnsatisfiedLinkError链接错误&#xff0c;原因可能有如下几种 类名错误包名错误方法名参数错误使用 JNI 协议调用&#xff0c;结果 dll 未实现 JNI 协…...

UDP(Echoserver)

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

论文浅尝 | 基于判别指令微调生成式大语言模型的知识图谱补全方法(ISWC2024)

笔记整理&#xff1a;刘治强&#xff0c;浙江大学硕士生&#xff0c;研究方向为知识图谱表示学习&#xff0c;大语言模型 论文链接&#xff1a;http://arxiv.org/abs/2407.16127 发表会议&#xff1a;ISWC 2024 1. 动机 传统的知识图谱补全&#xff08;KGC&#xff09;模型通过…...