思路：

大部分人第一反应就是晕，正常算法解决不了

考虑中间态，看看能不能有规律

      ·设D[i]为走到第i层走法的的种类数，

      ·则有D[1] =1, D[2] = 2,即下一层有1种走法，两层有2种走法。

      ·那么下三层D[3]就是下一层和下两层走法的和

      ·归纳可得D[i] = D[i-1] + D[i-2]，得到状态转移方程

代码：

int D[81] = {0}; //动态规划通常要保存子集的计算结果
int getStepSum( int n)
{
       //边界条件
       if( n == 1 || n ==2)
                 return n;
        //各递归子集的退出条件
        if(D[n] != 0) 
                return D[n];
         //子集状态变更
         D[n] = getStepSum(n-1) + getStepSum(n-2);
         return D[n];
}

注：实际编程会发现，返回值int溢出，需要将int 改成long long，这点在面试时需要考虑到

自底向上的解法

Long long D[81] = {0}; 

Long long getStepSum( int n)
{
          D[1] = 1;
          D[2] = 2;
          for(int i = 3; i<=n ; i++)
           {
                  D[i] = D[i-1] + D[i-2];
           }
           return D[n];
}