LeetCode 变态跳台阶问题

Question

题目描述

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

问题分析

假设 n>=2，第一步有 n 种跳法：跳 1 级、跳 2 级、到跳 n 级
跳 1 级，剩下 n-1 级，则剩下跳法是 f(n-1)
跳 2 级，剩下 n-2 级，则剩下跳法是 f(n-2)
……
跳 n-1 级，剩下 1 级，则剩下跳法是 f(1)
跳 n 级，剩下 0 级，则剩下跳法是 f(0)
所以在 n>=2 的情况下：
f(n)=f(n-1)+f(n-2)+...+f(1)
因为 f(n-1)=f(n-2)+f(n-3)+...+f(1)
所以 f(n)=2*f(n-1) 又 f(1)=1,所以可得 f(n)=2^(number-1)

示例代码

int JumpFloorII(int number) {
    return 1 << --number;//2^(number-1) 用位移操作进行，更快
}

补充

java 中有三种移位运算符：

1. “<<” : 左移运算符，等同于乘 2 的 n 次方
2. “>>”: 右移运算符，等同于除 2 的 n 次方
3. “>>>” : 无符号右移运算符，不管移动前最高位是 0 还是 1，右移后左侧产生的空位部分都以 0 来填充。与>>类似。

int a = 16;
int b = a << 2;//左移 2，等同于 16 * 2 的 2 次方，也就是 16 * 4
int c = a >> 2;//右移 2，等同于 16 / 2 的 2 次方，也就是 16 / 4