首页 > ACM题库 > 九度OJ > 剑指offer(04)-变态跳台阶[递推]
2013
12-09

剑指offer(04)-变态跳台阶[递推]

题目来自剑指offer系列 九度 1389

题目描述:
一只青蛙一次可以跳上1级台阶,也可以跳上2级……它也可以跳上n级。求该青蛙跳上一个n级的台阶总共有多少种跳法
输入:
输入可能包含多个测试样例,对于每个测试案例,输入包括一个整数n(1<=n<=50)。
输出:
对应每个测试案例,输出该青蛙跳上一个n级的台阶总共有多少种跳法。
样例输入:
6
样例输出:
32

当台阶数为n时,可以分为以下步骤来完成:

设第一次跳的台阶数为s,跳台阶方式数为T,则:
(1)s=1时,T(n) = T(n-1)
(2)s=2时,T(n) = T(n-2)
.
.
.
(n)s=n时,T(n) = T(0) = 1
所以总的跳台阶方式数T可以表示为:
T(n) = T(0) + T(1) + T(2) + … + T(n-1)
由于T(0) = T(1) = 1,所以T(n) = 2^(n-1)

#include<iostream>
#include<math.h>
using namespace std;
int main()
{int n;
while(cin>>n)
{long long result=(long long)pow(2,n-1);
cout<<result<<endl;
}
return 0;
}

 


  1. 老实说,这种方法就是穷举,复杂度是2^n,之所以能够AC是应为题目的测试数据有问题,要么数据量很小,要么能够得到k == t,否则即使n = 30,也要很久才能得出结果,本人亲测