跳台阶问题的分析

问题描述

    假设我们有两种方法来爬一个n级的台阶，我们可以一次爬一级台阶，也可以爬两级台阶。那么我们爬完这n级台阶总共有多少种方法呢？

 

分析

    关于这个问题的分析和讨论网上已经非常多了。这里一方面分析一下这个问题的本质，另外也对同类型的问题做一个总结概括。对于这种问题，我们先来看一些简单的情况，假设所有走法的函数为f(n)，在只有一级台阶的时候，我们的走法如下：

f(1) = 1， 因为我们只需要走一级台阶就到达了目的地。

而对于0级台阶，我们可以认为什么都不走也算一种走法，那么f(0) = 1。

再往后推导，那么f(2)呢？对于两级台阶来说，我们有如下的走法：

1. 每次走一级。 2. 一次走两级  所以f(2) = 2

    通过这几步的观察，我们可以发现一个如下规律：

    f(0) = 1

    f(1) = 1

    f(n) = f(n - 1) + f(n - 2)   n >= 2

    从我们观察的结果来看，这个递推关系构成了Fibonacci数列。当然，我们的这个推导是否就一定正确呢？我们可以通过数学归纳法来证明。假设我们这个跳台阶的关系成立，那么我们来针对两种情况考虑：

     基础情况： 对于n = 0, 1的情况，显然f(0) = 1, f(1) = 1, f(2) = f(0) + f(1)， 结论成立。

     假定对于数字n结论都成立，那么f(n) = f(n - 1) + f(n - 2)  (n >= 2)。 而此时，针对n + 1级台阶来说，能一步走到第n + 1级的台阶只能是首先走到了第n阶或者第n - 1阶。当走到第n阶的时候，只需要走一级台阶就达到了。而到第n-1阶的时候，只需要走两级台阶就达到了。所以它对应着走到第n阶再走一步，或者走到第n-1阶再走两个台阶。而当我们走到第n阶的时候，意味着我们这个时候的走法是f(n)，对应的，走到第n-1阶的时候走法是f(n - 1)。那么，这个时候我们走到第n+1级台阶总共的走法应该是f(n + 1) = f(n) + f(n - 1)。

    这样我们就证明了前面的这个推论。在前面的推导里，有人可能会有点疑惑，在第n - 1步的时候，既然前面有两个台阶到第n +1级，那么从这里一次走一个台阶到目的地这种走法为什么不能算呢？因为这个时候从n-1走一步到第n级的时候这个整体的走法已经包含在f(n)里面了。

    有了前面的这些推论，我们知道问题已经归结为怎么去计算Fibonacci数列。

Fibonacci数列问题

     根据前面的讨论，我们从这个数列的特性来实现怎么计算它们的所有走法。最典型的实现思路如下：

 

public static long fibonacci(int n) {
    if(n == 0) return 1;
    if(n == 1) return 1;
    return fibonacci(n - 1) + fibonacci(n - 2);
}

    我们知道，因为这里递归函数的关系为f(n) = f(n - 1) + f(n -2)，它的增长将很快，这种实现很容易导致堆栈溢出。至于这个函数会是一个什么样的形式，他们增长的有多快呢？我们后面会继续讨论。这里先把几种代码实现的思路记录下来。

 

    前面的代码实现是简单，不过问题在于大量的递归占用了空间，而实际上并没有用到那么多。我们完全可以把中间部分计算的结果保存起来，不需要重复的递归来计算。为了保存这个结果，我们可以采用一个长度为给定数字的数组。按照这种思路，我们实现的代码如下：

 

public static long f(int n) {
        if(n < 0)
            throw new IllegalArgumentException("Invalid n");
        long[] result = new long[n];
        result[0] = 1;
        result[1] = 1;
        if(n == 0) return 1;
        if(n == 1) return 1;
        for(int i = 2; i < n; i++) {
            result[i] = result[i - 1] + result[i - 2];
        }
        return result[n - 1];
    }

    这种代码实现的思路是保存了中间计算的结果，然后省略了很多重复计算的步骤。 从算法的时间复杂度来说，它会简单很多，只有O(n)。当然，从空间复杂度来说，它达到了O(n)。从代码里我们也看到，实际上每次我们用到的结果都是取一个元素它前面的两个，然后过去了之后再之前的就不用了。那么，这么点空间是否可以重复利用呢？如果可以的话，我们可以在时间复杂度不变的情况下，把占用的空间给缩减下来。下面是另外一个实现：

 

 

public static long compute(int n) {
        if(n < 0)
            throw new IllegalArgumentException("Invalid n");
        if(n == 0) return 1;
        if(n == 1) return 1;
        int first = 1, second = 1; 
        int sum = first + second;
        for(int i = 2; i < n; i++) {
            first = second;
            second = sum;
            sum = first + second;
        }
        return sum;
    }

     这部分的代码改进就在for循环里。每次我们将second赋值给first，然后将sum再赋值给second。采用一种滚动式向前推进的方式。只需要3个临时变量就解决了。

 

    当然，在这方面的讨论有很多，解决方法也有很多，这只是一种比较简单直接的办法而已。

 

进一步推导

    前面我们描述的Fibonacci问题它其实对应的是一种如下递归序列的一个特殊形式：

    f(n) = a1f(n - 1) + a2f(n-2) + ... + adf(n-d)。 对于这种递归函数，到底有没有一个直接的多项式函数形式的描述呢？相对来说，这是一个很复杂的问题，一种思路是可以建立特征值等式，然后建立一个方程组，结合递归函数的一些初始条件，比如f(0)=xxx f(1)=xxx来推导。这里基于的一个假设是f(n)最终应该会演化为一个多项式的形式，也就是f(n) = a1x^(n) + a2x^(n-1) + ...+ adx^(n-d) + an。

    因为这里的证明过于繁琐，可以参考后面的参考材料，这里就不再赘述。

 

总结

    跳台阶的问题解决思路其实就是绕了两步，第一步要推导出它们符合一个Fibonacci数列的特性。第二步则是要求这个Fibonacci数列的值。所以问题的焦点就变成对Fibonacci数列问题的分析。而且，对于这个数列的数学复杂度分析也比较有意思。它对应一个指数函数的级别，对它的推导曾经花了好几个世纪。

 

参考材料

mathematics for computer science