跳台阶问题

题目描述：

一个台阶总共有 n 级，如果一次可以跳 1 级，也可以跳 2 级。求总共有多少种跳法，并分析算法的时间复杂度。

分析和解法：

我们可以将原问题转化为斐波那契数列问题。

解法一：经典递归

我们把 n 级台阶时的跳法看成是 n 的函数，记为 f(n) 。

• 当 n = 1 时，f(n) = 1;
• 当 n = 2 时，f(n) = 2;
• 当 n > 2 时，f(n) = f(n-1) + f(n-2)

原来上述问题就转化为我们平常所熟知的 Fibonacci 数列问题了。
源代码如下：

#include <iostream>

using namespace std;

long long Fibonacci(int n)
{
    int result[3] = {0, 1, 2};
    if (n <= 2)
        return result[n];
        
    return Fibonacci(n - 1) + Fibonacci(n - 2);
}

int main()
{
    int n;
    cin >> n;
    cout << Fibonacci(n) << endl;
    return 0;
}

分析：时间复杂度约为 O（2 ^ n）。当然 Fibonacci 数列还有更快的实现算法。

解法二：从下往上计算

解法一之所以慢是因为重复的计算太多，只要避免重复计算就行了。比如我们可以把已经得到的数列中间项保存起来，如果下次需要计算的时候我们先查找一下，如果前面已经计算过了就不用再次计算了。更简单的办法是从下往上计算，首先根据 f(0) 和 f(1) 算出 f(2)，在根据 f(1) 和 f(2) 算出 f(3) ……依此类推就可以算出第 n 项了。很容易理解，这种思路的时间复杂度是 O(n) 。
源代码如下：

#include <iostream>

using namespace std;

long long Fibonacci_Solution2(unsigned n)
{
    int result[3] = {0, 1, 2};
    if (n <= 2)
        return result[n];

    long long  fibNMinusOne = 2;
    long long  fibNMinusTwo = 1;
    long long  fibN = 0;
    for(unsigned int i = 3; i <= n; ++ i)
    {
        fibN = fibNMinusOne + fibNMinusTwo;
        fibNMinusTwo = fibNMinusOne;
        fibNMinusOne = fibN;
    }
    return fibN;
}

int main()
{
    unsigned int n;
    cin >> n;
    cout << Fibonacci_Solution2(n) << endl;
    return 0;
}

分析：时间复杂度为 O（n）。

特别注意：

下面介绍一种时间复杂度是 O(logn) 的方法计算 Fibonacci 数列。（目前还没有修改适用于上面的问题）在介绍这种方法之前，先介绍一个数学公式：

Fibonacci 数列公式

因而计算 f(n) 就简化为了计算矩阵的 (n-2) 次方，而计算矩阵的 (n-2) 次方，我们又可以进行分解，即计算矩阵 (n-2) / 2 次方结果的平方，逐步分解下去，由于折半计算矩阵次方，因而时间复杂度为 O(log n) 。

#include <iostream>
#include <cassert>

using namespace std;

///////////////////////////////////////////////////////////////////////
// A 2 by 2 matrix
///////////////////////////////////////////////////////////////////////
struct Matrix2By2
{
    Matrix2By2
    (
        long long m00 = 0, 
        long long m01 = 0, 
        long long m10 = 0, 
        long long m11 = 0
    )
    :m_00(m00), m_01(m01), m_10(m10), m_11(m11) 
    {
    }

    long long m_00;
    long long m_01;
    long long m_10;
    long long m_11;
};

///////////////////////////////////////////////////////////////////////
// Multiply two matrices
// Input: matrix1 - the first matrix
//        matrix2 - the second matrix
//Output: the production of two matrices
///////////////////////////////////////////////////////////////////////
Matrix2By2 MatrixMultiply
(
    const Matrix2By2& matrix1, 
    const Matrix2By2& matrix2
)
{
    return Matrix2By2(
        matrix1.m_00 * matrix2.m_00 + matrix1.m_01 * matrix2.m_10,
        matrix1.m_00 * matrix2.m_01 + matrix1.m_01 * matrix2.m_11,
        matrix1.m_10 * matrix2.m_00 + matrix1.m_11 * matrix2.m_10,
        matrix1.m_10 * matrix2.m_01 + matrix1.m_11 * matrix2.m_11);
}

///////////////////////////////////////////////////////////////////////
// The nth power of matrix 
// 1  1
// 1  0
///////////////////////////////////////////////////////////////////////
Matrix2By2 MatrixPower(unsigned int n)
{
    assert(n > 0);

    Matrix2By2 matrix;
    if(n == 1)
    {
        matrix = Matrix2By2(1, 1, 1, 0);
    }
    else if(n % 2 == 0)
    {
        matrix = MatrixPower(n / 2);
        matrix = MatrixMultiply(matrix, matrix);
    }
    else if(n % 2 == 1)
    {
        matrix = MatrixPower((n - 1) / 2);
        matrix = MatrixMultiply(matrix, matrix);
        matrix = MatrixMultiply(matrix, Matrix2By2(1, 1, 1, 0));
    }

    return matrix;
}

///////////////////////////////////////////////////////////////////////
// Calculate the nth item of Fibonacci Series using devide and conquer
///////////////////////////////////////////////////////////////////////
long long Fibonacci_Solution3(unsigned int n)
{
    int result[2] = {0, 1};
    if(n < 2)
        return result[n];

    Matrix2By2 PowerNMinus2 = MatrixPower(n - 1);
    return PowerNMinus2.m_00;
}

int main()
{
    unsigned int n;
    cin >> n;
    cout << Fibonacci_Solution3(n) << endl;
    return 0;
}

参考资料：《编程之法》The Art of Programming By July
斐波那契数列时间复杂度分析