题解 | #跳台阶#

对于总数n，很容易穷举出所有组合的情况。

即{(n / 2)个2和(n % 2)个1，(n / 2 - 1)个2和(n % 2 + 2)个1……1个2和(n - 2)个1，0个2和n个1}

而a个1、b个2的全排列数为(a + b)! / (a! * b!)。

因此，可以得知每种组合对应的全排列数为等比数列，q = a * (a + b + 1) / ((b + 1) * (b + 2))；

所以，以下代码的时间复杂度为O(n)，空间复杂度为O(1)满足题目要求。

class Solution
{
public:
    // 求a个2, b个1的全排列数
    unsigned long long A(int a, int b)
    {
        unsigned long long res = 1;
        for (int i = a + b; i >= 1; --i)
        {
            if (i > a && i > b)
                res *= i;
            else if (i <= a && i <= b)
                res /= i;
        }
        return res;
    }
    int jumpFloor(int number)
    {
        int a = number >> 1;
        int b = number & 1;

        unsigned long long sum = 0;
        unsigned long long tmp = A(a, b);
        int i = 1;
        do
        {
            sum += tmp;
            tmp = tmp * a * (a + b + 1) / ((b + 1) * (b + 2));
            --a;
            b += 2;
        } while (a >= 0);
        // return A[(n/2), (n/2) + (n%2)]...A[(n/2-k), (n/2-k) + (n%2+2*k)]...A[0, n]
        return sum;
    }
};

当然，上面的解法很难想到。用状态方程求解思路更加清晰，这个状态方程中 f(n - 2) 的值用过一次就不会再用了，所以可以将其覆盖以节省空间，优化后就只剩三个变量了(有人称之为滚动数组)。

class Solution
{
public:
    int jumpFloor(int number)
    {
        // f(n)表示跳n阶的总跳法
        // f(n) = f(n - 1) + f(n - 2)
        // f(1) = 1
        // f(2) = 2

        int a = 1, b = 2, res = a + b;
        if (number == 1) return a;
        else if (number == 2) return b;
        for (int i = 3; i < number; ++i)
        {
            a = b;
            b = res;
            res = a + b;
        }
        return res;
    }
};