上台阶问题

转载请注明出处：http://www.cnblogs.com/zhishoumuguinian/p/8342382.html

思路：爬上最后一节台阶有两种情况，第一种走一级上到最后一节台阶，第二种走两级上到最后一节台阶。于是，所有的上台阶走法我们可以分解为上n-1级台阶的走法（第一种情况）加上n-2级台阶的走法（第二种情况）。于是有了递推式f(n)=f(n-1)+f(n-2)，而递推的结束条件为n=1时 f(n)=1; n=2时， f(n)=2。

方法一：递规

 1 #include<iostream>
 2 
 3 using namespace std;
 4 int fstep(int n)
 5 {
 6     if(n==1)
 7         return 1;
 8     if(n==2)
 9         return 2;
10     if(n>=3)
11         return fstep(n-2)+fstep(n-1);
12     return 0;
13 }
14 int main()
15 {
16     int n,step;
17     cout<<"input the steps of the stair:"<<endl;
18     cin>>n;
19     step=fstep(n);
20     cout<<"The methods to finish the stair are: "<<step<<endl;
21     return 0;
22 }

方法二：动态规划

 1 #include <iostream>
 2 #include <string.h>
 3 using namespace std;
 4 int step[1005];//设置一个数组保存计算过的n 节台阶上法，避免重复计算
 5 int fstep(int n)
 6 {
 7     if(n==0)
 8         step[n]=1;
 9     if(n==1)
10         step[n]=1;
11     if(step[n]==0)//如果n节台阶没被计算过，执行下列语句，已经被计算过了，直接返回就可。
12         step[n]=fstep(n-1)+fstep(n-2);
13     return step[n];
14 }
15 
16 int main()
17 {
18     int n;
19     memset(step,0,sizeof(step));
20     cout<<"input the steps of the stair:"<<endl;
21     cin>>n;
22     cout<<"The methods to finish the stair are: "<<fstep(n)<<endl;
23     return 0;
24 }

方法三：斐波那契数列

 1 #include <iostream>
 2 
 3 using namespace std;
 4 
 5 int main()
 6 {
 7     int fstep[1005];
 8     int n=0;
 9     fstep[1]=1,fstep[0]=1;
10     for(int i=2; i<1000; i++)
11     {
12         fstep[i]=fstep[i-1]+fstep[i-2];
13     }
14     cout<<"input the steps of the stair:"<<endl;
15     cin>>n;
16     cout<<"The methods to finish the stair are: "<<fstep[n]<<endl;
17     return 0;
18 }