剑指offer-9-变态跳台阶

题⽬描述

⼀只⻘蛙⼀次可以跳上1 级台阶，也可以跳上2级……它也可以跳上n级。求该⻘蛙跳上⼀个n级的台阶总共有多少种跳法。
思路及解答

数学归纳法

⾸先⻘蛙⼀次可以跳 1 , 2 , 3 到 n 级。假设函数是f(n) ，则：

• ⻘蛙跳到第⼀级是f（1）=1 ，只有⼀种跳法。
  
• ⻘蛙跳到第⼆级，可以是直接跳到第⼆级，也可以是从第⼀级直接跳。所以f(2)=f(1)+1
  
• ⻘蛙跳到第三级，可以从第0 级跳，也可以从第1级跳，也可以从第2 级跳。所以f(3)=f(1)+f(2)+1 ;
  
• 依次类推，⻘蛙跳到第n 级，可以是从0 , 1 , 2 , 3 .. (n-1) 级跳，所以f(n)=f(1)+f(2)+f(3)...+f(n-1)+1 ;
  

进一步观察可以发现：

• f(1) = 1
  
• f(2) = f(1) + f(0) = 2
  
• f(3) = f(2) + f(1) + f(0) = 4
  
• f(4) = f(3) + f(2) + f(1) + f(0) = 8
  

显然，这是一个等比数列，通项公式为f(n) = 2^(n-1)。这个发现将问题简化为简单的幂次计算
[code]public class Solution {    public int JumpFloorII(int target) {                        if (target