一个人上台阶可以一次上1个，2个，或者3个，问这个人上n层的台阶，总共有几种走法？

关于此题：看到此题，我，们显然不会害怕，因为在怎么不会，最简单的穷举法总是可以的是吧！也就是说：令 x， y， z分别为1， 2， 3步的数目，那么最多有n个一步即x <= n;那么最多有n/2步2步，即y <= n/2，那么最多有n/3步，即z <= n/3；所以进行遍历就是咯：

for( int x = 0; x <= n; x++ )

{

      for( int y = 0; y < n/2; y++ )

      {

           for( int z = 0; z < n/3; z++ )

           {

                if( x + 2 * y + 3 * z == n )

                {

                  //! 合格的排序，可以输出

                }

           }

      }

}

 

当然大家知道上面的办法是非常浪费时间的，时间复杂度是O( n ^ 3 )；所以不可取，O(∩_∩)O~

 

假设每次走一个或者两个台阶，共50级：

费波拉希数列：

一共1个台阶的话有1种走法.

一共2个台阶的话有2种走法.

一共3个台阶的话有3种走法.

一共4个台阶的话有5种走法.

一共5个台阶的话有8种走法.

一共6个台阶的话有13种走法.

一共7个台阶的话有21种走法.

一共8个台阶的话有34种走法.

一共9个台阶的话有55种走法.

一共10个台阶的话有89种走法.

一共11个台阶的话有144种走法.

一共12个台阶的话有233种走法.

一共13个台阶的话有377种走法.

一共14个台阶的话有610种走法.

一共15个台阶的话有987种走法.

一共16个台阶的话有1597种走法.

一共17个台阶的话有2584种走法.

一共18个台阶的话有4181种走法.

一共19个台阶的话有6765种走法.

一共20个台阶的话有10946种走法.

一共21个台阶的话有17711种走法.

一共22个台阶的话有28657种走法.

一共23个台阶的话有46368种走法.

一共24个台阶的话有75025种走法.

一共25个台阶的话有121393种走法.

一共26个台阶的话有196418种走法.

一共27个台阶的话有317811种走法.

一共28个台阶的话有514229种走法.

一共29个台阶的话有832040种走法.

一共30个台阶的话有1346269种走法.

一共31个台阶的话有2178309种走法.

一共32个台阶的话有3524578种走法.

一共33个台阶的话有5702887种走法.

一共34个台阶的话有9227465种走法.

一共35个台阶的话有14930352种走法.

......

这不正是个费波拉希数列！！！！

 知道这个数学规律就好办了。代码如下：

        function fib(n) {
            return function(n, a, b) {
                return n > 0 ? arguments.callee(n - 1, b, a + b) : a;
            } (n, 0, 1);
        }
        fib(0); //0
        fib(1); //1
        fib(2); //1
        fib(3); //2
        fib(4); //3
        //......
        fib(50); //12586269025
        fib(51); //20365011074,这里是上到第50个阶梯

所以现在我们需要想办法了吧，那么可以按照数学的思维来解题，找找规律吧：如果是一阶楼梯，就是1 步，如果是二阶楼梯就是1步或者2步即2种方法，如果是三阶楼梯就是1 1 1、 1 2、 2 1、 3四种方法，那么到了四阶我们就知道，就是可以从1或者2或者3处直接到4，那么就是fun( 1 ) + fun( 2 ) + fun( 3 )( fun( x )意思就是到达第X个楼梯的方法 )；所以此题我们看到就是类似于 “ 斐波那契数列 ”的规律，所以找到这样的规律，就好办了~  可以编码如下：

int  fun( int n )

{

      if( n == 1 )

      {

            return 1;

      } 

      if( n == 2 )

      {

            return 2;

      } 

      if( n == 3 )

      {

          　return 4; 

      }

 

      return (　fun( n - 1 ) + fun(n - 2 ) + fun( n - 3 ) ); 

}