剑指Offer（09）：变态跳台阶

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

一级&＃xff1a;1 &＃xff08;1种&＃xff09;
二级&＃xff1a;1&＃43;1&＃xff0c;2 &＃xff08;2种&＃xff09;
三级&＃xff1a;1&＃43;1&＃43;1&＃xff0c;2&＃43;1&＃xff0c;1&＃43;2&＃xff0c;3 &＃xff08;4种&＃xff09;
四级&＃xff1a;1&＃43;1&＃43;1&＃43;1&＃xff0c;2&＃43;1&＃43;1&＃xff0c;1&＃43;2&＃43;1&＃xff0c;1&＃43;1&＃43;2&＃xff0c;3&＃43;1&＃xff0c;1&＃43;3&＃xff0c;2&＃43;2&＃xff0c;4 &＃xff08;8种&＃xff09;
…
如上不难看出f(n)&＃61;2^(n-1)。可以用移位运算符。

public class Solution {public int JumpFloorII(int target) {return 1 << target - 1;
// return (int) Math.pow(2, target - 1);}
}