下台阶问题

/*
 * 有个楼梯,长度为length,有人下楼,一次走一步或者一次走两步,问有多少种方法,用具体的方法实现
 */
#include<stdio.h>
#include<stdlib.h>

int getcount(int length)
{
  if(length==1)return 1;
  else if(length==2)return 2;
  else return getcount(length-1)+getcount(length-2);
}

int main()
{
  int length=3;
  int count=getcount(length);
  printf("count=%d\n",count);
}

 

评论

3 楼 Algorithm123 2011-01-25  

刚才自顶向下的备忘录方法还没写完就误传了：
下面改正如下：

int getCount[length+1]={0};  
getCount[1]=1;getCount[2]=2;  
int getcount(int length)    
{    
  if(getCount[length]!=0)  
      return getCount[length];    
  else 
      return getCount(length-1)+getCount(length-2);    
}    

2 楼 Algorithm123 2011-01-25  

1.解决该问题的表达式很容易推出：T(n)=T(n-1)+T(n-2)
2.如果按上述递归法实现，则复杂度为T(n)=T(n-1)+T(n-2)≤2T(n-1)，故T(n)=O(2^n)，是指数级的
3.若考虑动态规划的实现方法，可以避免重复的计算，则很容易在线性时间内实现，用动态规划可以通过如下两种方法:自底向上和自顶向下的备忘录方法：
自底向上：

int getCount[length+1]={0};
getCount[1]=1;getCount[2]=2;
for(int i=3;i<=length;i++)
    getCount[i]=getCount[i-1]+getCount[i-2];

自顶向下的备忘录方法:

int getCount[length+1]={0};
getCount[1]=1;getCount[2]=2;
int getcount(int length)  
{  
  if(length==1)
return 1;  
   
  else return getcount(length-1)+getcount(length-2);  
}  

1 楼 tg008007x3 2010-12-27