面試被問到問題－Truly Madly Deeply

被問到n個樓階每次只能走2步或1步有幾種走法
可惜當時腦袋茫然從被提醒recursive要怎麼做就沒搞懂原由

其實這也算蠻典型的遞迴問題但太久沒碰
無法聯想要怎麼做

遞迴作法
int step(int n)
{
if(n==1) //先走一步的方法數
return 1;

else if(n==2) //先走兩步的方法數
return 2;

if(n>2)
return step(n-1)+step(n-2)
}

被問到轉換成loop該怎麼做腦袋空白亂答一通
走到捷運已經知道自己錯了覺得好羞愧　才想到作法

int Step(int n)
{

int step[2]; //方法數
int temp;

   //initialize
   step[0]=1; //走一步方法數
   step[1]=2; //走兩步方法數

   if(n==1) //只有一階
     step[1]=1;
   else if(n==2) //只有二階
     step[1]=2;
   else if(n<1) //無階
     step[1]=0;
   else
   {
　   //轉成像遞迴形式 step[n]=step[n-1]+step[n-2]
　   for(i=3;i<=n;i++)
　   {
    　 temp=step[1];
        step[1]=step[0]+step[1];//走第i步需要的方法數存回step[1]
    　 step[0]=temp;
　   }
   }
   return step[1];
}