剑指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)。这个发现将问题简化为简单的幂次计算
public class Solution { public int JumpFloorII(int target) { if (target
页:
[1]