題目描述
一只青蛙一次可以跳上1級臺階，也可以跳上2級……它也可以跳上n級。求該青蛙跳上一個n級的臺階總共有多少種跳法闸天。
/**
* Created by ZengXihong 2019-06-03.
* 題目描述
一只青蛙一次可以跳上1級臺階犬绒，
也可以跳上2級……它也可以跳上n級。
求該青蛙跳上一個n級的臺階總共有多少種跳法挂签。
f(n) = f(n-1) + f(n-2) + ... + f(1)
f(n-1) = f(n-2) + f(n-3) + ... + f(1)
f(n) - f(n-1) = f(n-1)
f(n) = 2 * f(n-1)
*/
public class Solution9 {
public int JumpFloorII(int target) {
if(target <= 1){
return target;
}
return 2 * JumpFloorII(target-1);
}
public int JumpFloorII2(int target) {
/**
青蛙一次可以跳上1級臺階疤祭，
也可以跳上2級,也可以跳上n級。
換個說法饵婆，除了第n級臺階青蛙是最終的勺馆，
其他n-1級臺階青蛙都有兩種可能，跳 和 不跳
這就轉(zhuǎn)化成了一個排列組合問題，
故一共有2^(n-1)種方法草穆，采用移位計算該值
*/
return 1<<(target-1);
}
}
