Jobdu 1389 - 剑指offer(16)-变态跳台阶[递推] | Acm之家

九度OJ-题目1389：变态跳台阶
剑指offer(16)-变态跳台阶[递推] | Acm之家

一只青蛙一次可以跳上1级台阶，也可以跳上2级……它也可以跳上n级。求该青蛙跳上一个n级的台阶总共有多少种跳法。

当台阶数为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)
http://blog.csdn.net/pengyan0812/article/details/46343171

(1) 如果青蛙选择跳上1级台阶，则剩下的台阶数目是n - 1, 跳上一个n – 1级的台阶的跳法数目是f(n - 1)；
(2) 如果青蛙选择跳上2级台阶，则剩下的台阶数目是n - 2, 跳上一个n – 2级的台阶的跳法数目是f(n - 2)；
(3) 如果青蛙选择跳上3级台阶，则剩下的台阶数目是n - 3, 跳上一个n – 3级的台阶的跳法数目是f(n - 3)；
……
(n - 1) 如果青蛙选择跳上n - 1级台阶，则剩下的台阶数目是1, 跳上一个1级的台阶的跳法数目是f(1)；
(n) 如果青蛙选择跳上n级台阶，则剩下的台阶数目是0, 跳上一个0级的台阶的跳法数目是f(0)。
因此可以得知,
f(n) = f(n-1) + f(n-2) + ... + f(2) + f(1) + f(0)                                                           [1]
f(n-1) = f(n-2) + f(n-3) + ... + f(1) + f(0)                                                                 [2]
……                                                                                                                     ......
f(2) = f(1) + f(0)                                                                                                     [n-2]
f(1) = f(0)                                                                                                              [n-1]
f(0) = 1                                                                                                                  [n]
由公式[1]和公式[2]可以推出
f(n) = f(n-1) + f(n-1) = 2 * f(n-1)。
对于公式[n]：f(0) = 1，我是这样理解的：青蛙在跳上一个只有1级的台阶时，只有跳上1级台阶这一个选择，而剩余台阶数目为0，因此可以得出f(1) = f(0) = 1，所以可推出以下公式：

X. 

06	while(cin>>n)

07	{  long long result=(long long)pow(2,n-1);

08	cout<<result<<endl;

09

}

X. Precompute

1. ** 
2. * 计算出青蛙跳上一个n级的台阶总共有多少种跳法 
3. * f(n) = f(n-1) + f(n-2) + ... + f(2) + f(1) + f(0) ---->  f(n) = 2*(f(n-1))   // n >= 2 
4. * @param jumpMethods  用于保存跳台阶的跳法数目 
5. * @return void 
6. */  
7. void getNumberOfSuperJumpSteps(long long * jumpMethods)  
8. {  
9.     int i;  
10.     jumpMethods[1] = 1;  
11.     for(i = 2;i <= 50;i++)  
12.     {  
13.        jumpMethods[i] = 2 * jumpMethods[i - 1];  
14.     }  
15. }  

1.     while(EOF != scanf("%d",&n))  
2.     {  
3.         printf("%lld\n",jumpMethods[n]);  
4.     }

Read full article from 剑指offer(16)-变态跳台阶[递推] | Acm之家