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

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

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

剑指offer算法题

贪心算法，变态跳台阶
题目描述
一只青蛙一次可以跳上1级台阶，也可以跳上2级……它也可以跳上n级。求该青蛙跳上一个n级的台阶总共有多少种跳法。

题目分析
方法一
通过分析可以发现，跳到当前第n个台阶的跳法数量等于跳到前面第n-1个台阶的跳法数量加上最后一次一步跳到当前台阶跳法，也就是说：

f(n) = f(1)+f(2)+...+f(n-2)+f(n-1)+1

①式

同理可得： f(n-1) = f(1)+f(2)+...+f(n-2)+1

②式

①式-②式可得： f(n) = 2f(n-1)

下面是JAVA算法实现：

public int JumpFloorII(int target) {int result = 0;if(target <= 0){result = target;return result;}else if(target == 1){result = target;return result;}else{result = 2 * JumpFloorII(target - 1);return result;}
}

方法二
通过分析可以得到，每个台阶都有跳和不跳两个选择，除了最后一个台阶必须要跳，其余台阶都具有两个选择，所以：

f(n) = 2^(n-1) 下面是JAVA算法实现：

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