首页 > 其他分享 >小明爬楼梯(1)(递推)

小明爬楼梯(1)(递推)

时间:2024-05-25 17:05:18浏览次数:20  
标签:小明 楼底 爬楼梯 int 到达 阶梯 递推

题目描述

小明很喜欢爬楼梯,但是小明腿不够长,每次小明最多只能一步跨越两个阶梯。比如他初始在楼底,跨越一个阶梯到达 1号阶梯,或者跨越两个阶梯到达 2 号阶梯。

为了选出一种最轻松的爬楼梯的方式,小明想把所有不同的到达楼顶的方式都尝试一遍。对于一共有 n 个阶梯的楼梯,小明一共有多少总方法从楼底到达楼顶。

由于最后答案可能很大,输出最后的答案对100007 取模的结果。

输入格式

第一行输入一个整数 n(1≤n≤1000)。

输出格式

输出最后答案对于100007 取模的结果。

题解

每层楼梯方式数量

  1. 1
  2. 2
  3. 3
  4. 5
  5. 8
  6. 13

.......

由此可推出该数列是一个斐波那契数列(a[i]=a[i-1]+a[i-2]);

代码

60分代码

#include<bits/stdc++.h>
using namespace std;
int a[1001];
int main(){
	int n;
	cin>>n;
    a[1]=1;
    a[2]=2;
    for(int i=3;i<=n;i++){
        a[i]=(a[i-1]+a[i-2]);
    }
    cout<<a[n]%100007;
	return 0;
}
​

由于 n非常大,所以会导致int爆;

AC代码

#include<bits/stdc++.h>
using namespace std;
int a[1001];
int main(){
	int n;
	cin>>n;
    a[1]=1;
    a[2]=2;
    for(int i=3;i<=n;i++){
        a[i]=(a[i-1]+a[i-2])%100007;
    }
    cout<<a[n]%100007;
	return 0;
}

点个关注吧!!!!!!!!!!!!! 

标签:小明,楼底,爬楼梯,int,到达,阶梯,递推
From: https://blog.csdn.net/jerrywinwin/article/details/139199840

相关文章

  • 03_使用最小花费爬楼梯
    746.使用最小花费爬楼梯旧题目描述:数组的每个下标作为一个阶梯,第i个阶梯对应着一个非负数的体力花费值cost[i](下标从0开始)。每当你爬上一个阶梯你都要花费对应的体力值,一旦支付了相应的体力值,你就可以选择向上爬一个阶梯或者爬两个阶梯。请你找出达到楼层顶部的最低花费......
  • 学习笔记:生成函数II(集合分拆、置换、整数分拆、它们的递推公式、生成函数 和快速计算)
    形式幂级数的更多运算形式幂级数与幂级数的比较形式幂级数本质是序列(\(x^i\)无意义),幂级数本质是极限。形式幂级数通过带入\(x\)还原成幂级数。假设系数在\(\mathbb{C}\)上,可以证明形式幂级数与具有正收敛半径的幂级数在'通常'的所有运算上服从同样规律(加减乘除求导积......
  • FFT 优化常系数齐次线性递推式
    \(f_i\)序列满足\(f_i=\displaystyle\sum_{j=1}^kc_jf_{i-j}\)。\(k\le32000,n\le10^9\)。已知\(f_1\simf_k\)和\(c_1\simc_k\)。求\(f_n\)。这称为"\(k\)次齐次常系数线性递推式"。如果\(k\)比较小,可以用矩阵快速幂;但\(k\)太大,一次矩阵乘法都很慢。我们可......
  • 第?课——基于矩阵快速幂的递推解法
    第?课——基于矩阵快速幂的递推解法由于中间的数论部分我自己学的很差,没有办法写出清晰的博客来,所以这里跳过了数论部分的博客,来到矩阵快速幂。递推递推是一个非常常用的工具。比如经典的斐波那契数列:\[f(x)=\left\{\begin{array}{**lr**}1&,0\l......
  • 力扣746.使用最小花费爬楼梯
    题目给你一个整数数组cost,其中cost[i]是从楼梯第i个台阶向上爬需要支付的费用。一旦你支付此费用,即可选择向上爬一个或者两个台阶。你可以选择从下标为0或下标为1的台阶开始爬楼梯。请你计算并返回达到楼梯顶部的最低花费解题思路​ 动态规划1.首先需要明确,先支付......
  • leetcode算法热题-爬楼梯
    题目假设你正在爬楼梯。需要n阶你才能到达楼顶。每次你可以爬1或2个台阶。你有多少种不同的方法可以爬到楼顶呢?示例1:输入:n=2输出:2解释:有两种方法可以爬到楼顶。1阶+1阶2阶示例2:输入:n=3输出:3解释:有三种方法可以爬到楼顶。1阶+1阶+1阶1......
  • 38天【代码随想录算法训练营34期】第九章 动态规划part01 (● 理论基础 ● 509. 斐波
    理论基础斐波那契数classSolution:deffib(self,n:int)->int:ifn==0:return0ifn==1:return1returnself.fib(n-1)+self.fib(n-2)爬楼梯classSolution:defclimbStairs(self,n:int)->i......
  • 洛谷题解-官方题单-递归与递推
    P1255数楼梯原题链接题目描述楼梯有N阶,上楼可以一步上一阶,也可以一步上二阶。编一个程序,计算共有多少种不同的走法。对于60%的数据,N≤50;对于100%的数据,1≤N≤5000。思路:每次有2种方法上楼梯,要么上一阶,要么上二阶。第一种:得50分的做法是可以用递归来解:点击查看代码......
  • P8990 [北大集训 2021] 小明的树
    MyBlogsP8990[北大集训2021]小明的树首先连通块个数可以用经典的点边转化,用点的个数减去边的条数。观察之后可以发现定合法的充要条件是黑色的点构成一个连通块,同样使用点边转化。现在可以看成有两个序列(时间轴),\(V\)和\(S\),操作是区间\(v\)的修改,区间\(s\)的修改,和......
  • 信息学奥赛一本通题目解析:1204:爬楼梯(记忆化递归)
    【题目描述】树老师爬楼梯,他可以每次走1级或者2级,输入楼梯的级数,求不同的走法数。例如:楼梯一共有3级,他可以每次都走一级,或者第一次走一级,第二次走两级,也可以第一次走两级,第二次走一级,一共3种方法。【输入】输入包含若干行,每行包含一个正整数N,代表楼梯级数,1≤N≤30。【......