九度OJ—題目1205：N階樓梯上樓問題 (非遞歸)

基本思路：

走到第n階時可能是從第n-1階走一步到的，也可能是從n-2階走兩階到的，設F(n)為走到n階的種數，則F(n)=F(n-1)+F(n-2).

這是一個動態規劃的問題，其實就是一個斐波那契數列。

由於題中規定不能用遞歸的方式解，本來規定時間限制1s，遞歸估計也肯定超時。

又因為N<90，勢必會最後來個大數處理，用long long 類型數據。

    #include   
       
    int main()  
    {  
            int i,N;  
            long long a[90];  
            while(~scanf("%d",&N))  
            {               
                    a[1]=1;  
                    a[2]=2;  
                    for(i=3;i<=N;i++)  
                            a[i]=a[i-1]+a[i-2];  
                    printf("%lld\n",a[N]);  
            }  
               
            return 0;  
               
    }  
    /************************************************************** 
        Problem: 1205 
        User: vhreal 
        Language: C 
        Result: Accepted 
        Time:0 ms 
        Memory:912 kb 
    ****************************************************************/