題目描述
一只青蛙一次可以跳上1級臺階，也可以跳上2級。求該青蛙跳上一個n級的臺階總共有多少種跳法（先后次序不同算不同的結果）。
解法一（效率最高）
數學歸納法：
public class Solution {public int JumpFloor(int target) {if(target == 1 || target == 2) {return target;}int s1 = 1,s2 = 2,s3 = 0;for (int i = 3; i <= target; i++) {s3 = s1 + s2;s1 = s2;s2 = s3;}return s3;} }
?解法二：遞歸解法（耗時）
public class Solution {public int JumpFloor(int target) {if(target == 1 || target == 2) {return target;} else {return JumpFloor(target - 1) + JumpFloor(target - 2);}} }
變態跳臺階
一只青蛙一次可以跳上1級臺階，也可以跳上2級……它也可以跳上n級。求該青蛙跳上一個n級的臺階總共有多少種跳法。
繼續用數學歸納法求解：
f(n) = f(n - 1) + f(n - 2) + ... + f(1)?
f(n - 1) =?f(n - 2) + ... + f(1)?
即f(n) = 2f(n-1)
public class Solution {public int JumpFloorII(int target) {if(target == 1 || target == 2) {return target;} else {return 2<<(target-2);}} }
?
?
