JZ9 — 变态跳台阶

题目描述

一只青蛙一次可以跳上1级台阶，也可以跳上2级……它也可以跳上n级。求该青蛙跳上一个n级的台阶总共有多少种跳法。

题目分析

由题目易得f[n] = f[n-1] + f[n-2] + ... + f[1] + 1
如果不知道这个结论是怎么得到的，可以参考上一题：http://www.guanhaobo.cn/?p=686

f[1] = 1
f[2] = f[1] + 1 = 2 * f[1]
f[3] = f[2] + f[1] + 1 = 2 * f[2]
f[4] = f[3] + f[2] + f[1] + 1 = 2 * f[3]

易得f[n] = 2 * f[n-1]
所以直接递归或递推就可以解决本题，不再赘述。

这里介绍一种更快的方法，由f[n] = 2 * f[n-1]和f[1] = 1易得f[n] = pow(2, (n - 1))，即2的n - 1次幂。
计算幂的时候，可以使用快速幂算法加快速度。

例如求3的50次方：易得50的二进制形式为110010，即50 = 110010B = 100000B + 10000B + 10B，即pow(3, 50) = pow(3, 32) * pow(3, 16) * pow(3, 2)。因此先求出pow(3, 2)，再利用pow(3, 2)求出pow(3, 16)，最后通过pow(3, 16)求出pow(3, 32)即可。
事实上，易得pow(a, pow(2, n)) = pow(a, pow(2, n-1)) * pow(a, pow(2, n-1))，例如pow(a, 1000B) = pow(a, 100B) * pow(a, 100B).

这个算法的主要思想就是通过指数的二进制形式，巧妙地将结果分解为若干个乘积，即指数的二进制形式下为1的位置对应的值。
求base的number次幂，具体策略如下：
当number > 0时，执行以下循环
1. 对number和1进行按位与操作。如果等于1，说明number的二进制形式在当前位置为1，令ans = ans * base
2. 令base = base * base
3. 对number进行二进制移位操作，右移一位。即number = number >> 1

C语言实现如下：

// 求base的number次幂
int quickpow(int base, int number)
{
    int ans = 1;
    while (number)
    {
        if (number & 1)
            ans *= base;
        base *= base;
        number >>= 1;
    }
    return ans;
}

我们会发现，循环次数其实就是number的二进制形式的长度，因此时间复杂度为O(log(n))

C++

class Solution
{
public:
    int jumpFloorII(int number)
    {
        int base = 2, ans = 1;
        number--;
        while (number)
        {
            if (number & 1)
                ans *= base;
            base *= base;
            number >>= 1;
        }
        return ans;
    }
};

Java

public class Solution {
    public int JumpFloorII(int target) {
        int base = 2, ans = 1;
        target--;
        while (target > 0) {
            if ((target & 1) == 1)
                ans *= base;
            base *= base;
            target >>= 1;
        }
        return ans;
    }
}