如果一次可以跳任意阶,那么要想跳到第n阶,可以从前面任意一阶跳过去,即f(n)=f(n-1)+f(n-2)+……+f(2)+f(1)。
同理,f(n-1)=f(n-2)+f(n-3)+……+f(2)+f(1), 那么f(n) = 2 * f(n-1).
依此类推,f(n-1)=2 * f(n-2), …… f(2) = 2 * f(1), 而f(1) = 1;
故,f(n)=2 ^ (n-1);
int jumpFloorII(int number ) { if(number < 0) return -1; else if(number == 0 || number == 1) return 1; else // return 2 * jumpFloorII((number - 1)); //这是用递归的方法表示,比较慢 return 1<<(number-1); //用移位的方法表示2的幂就快一些 }