HDU2041超级楼梯（递归）（简单动态规划）（斐波那契）

Love The Way You Lie 2022-05-25 02:42 105阅读 0赞

# 超级楼梯 #

**Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 65536/32768 K (Java/Others)  
Total Submission(s): 71947 Accepted Submission(s): 36678**

Problem Description

有一楼梯共M级，刚开始时你在第一级，若每次只能跨上一级或二级，要走上第M级，共有多少种走法？

Input

输入数据首先包含一个整数N，表示测试实例的个数，然后是N行数据，每行包含一个整数M（1<=M<=40）,表示楼梯的级数。

Output

对于每个测试实例，请输出不同走法的数量

Sample Input

2 2 3

Sample Output

1 2

**一共有 m 个台阶楼梯，每次只能够跨一级或二级  
  
  
我们这样考虑  
假设一共有 10 个台阶楼梯，只差最后一步就能走到第十个台阶  
这个时候只会出现两种情况：  
9-->10  
8-->10  
  
  
定义 f(m) := 到达 m 个台阶需要的走法数目  
所以 f(10) = f(9) + f(8)  
  
  
  
  
其中f(1)=1  
 f(2)=1  
  
..........  
  
  
不废话了，其实就是斐波那契数  
也就是简单地动态规划  
状态转移方程：f(m)=f(m-1)+f(m-2)  
边界：  
f(1)=1  
f(2)=1**

完全理解了这些简单问题，对于递归和动态规划帮助很大

#include<cstdio>
    using namespace std;
    typedef long long ll;
    ll a[60];
    int main()
    {
    	a[0]=1;a[1]=1;
    	for(int i=2;i<60;i++)	a[i]=a[i-1]+a[i-2];
    	int t,m,n;
    	scanf("%d",&t);
    	while(t--)
    	{
    		scanf("%d",&n);
    		printf("%lld\n",a[n-1]);
    	}
    	return 0;
    }

发表评论取消回复

表情：

评论列表（有 0 条评论，105人围观）

还没有评论，来说两句吧...

相关阅读

相关斐波那契数列 - 动态规划

斐波那契数列写一个函数，输入 n ，求斐波那契（Fibonacci）数列的第 n 项。斐波那契数列的定义如下： F(0) = 0, F(1) = 1 F(N) =

妖狐艹你老母/ 2022年12月16日 13:05/ 0 赞/ 172 阅读

相关数楼梯（递归与递推）（斐波那契数列）

需要求斐波那契数列的第5000项，基本上1000项左右long long 就爆炸了。看代码，高精度还得去练一练。复习一下斐波那契数列的通项公式： ![在这里插入图

迷南。/ 2022年11月13日 01:52/ 0 赞/ 199 阅读

相关斐波那契数列(递归思想)

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhp

矫情吗；*/ 2022年11月11日 06:13/ 0 赞/ 223 阅读

相关超级楼梯 HDU - 2041

超级楼梯 HDU - 2041 -------------------- Problem 有一楼梯共M级，刚开始时你在第一级，若每次只能跨上一级或二级，要走上第M

- 日理万妓/ 2022年06月14日 10:27/ 0 赞/ 111 阅读

相关 HDU2041超级楼梯（递归）（简单动态规划）（斐波那契）

超级楼梯 Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 65536/32768 K (Java/Others)

Love The Way You Lie/ 2022年05月25日 02:42/ 0 赞/ 106 阅读

相关 python 递归实现斐波那契

斐波那契 def f(n): if n == 1 or n == 2: return 1

超、凢脫俗/ 2022年05月19日 11:14/ 0 赞/ 174 阅读

相关递归算法--斐波那契数列

大家都知道斐波那契数列，现在要求输入一个整数n，请你输出斐波那契数列的第n项（从0开始，第0项为0）。n<=39 很容易我们想到使用递归求解： public

刺骨的言语ヽ痛彻心扉/ 2022年05月18日 01:06/ 0 赞/ 211 阅读

相关动态规划斐波那契

运用动态规划描述斐波那契数列，运用动态规划使得问题简化，运算速度大幅提升。 private static int fib(int n) { if(n==

淩亂°似流年/ 2022年02月02日 11:15/ 0 赞/ 233 阅读

相关递归求斐波那契数列

斐波那契数列题目描述：编写一个函数，求斐波那契数列的第n项的值。首先，对于斐波那契数列，我们是非常熟悉了，对斐波那契定义为如下：f(0)=0,f(1)=0,f(2)=1

左手的ㄟ右手/ 2021年11月17日 12:34/ 0 赞/ 363 阅读

相关斐波那契_尾递归

(1)计算任意数n的阶乘 5! 54321 8! 87654321 ''' 递归函数通过两个条件出发回的过程: (1) 当

悠悠/ 2021年11月13日 18:50/ 0 赞/ 294 阅读