劍指offer： 變态跳台階

題目描述

一隻青蛙一次可以跳上1級台階，也可以跳上2級……它也可以跳上n級。求該青蛙跳上一個n級的台階總共有多少種跳法。 思路：由前幾項得到：1,2,4,8是以得出規律： JumpFloorII(target)=2*JumpFloorII(target-1)；

方法1：遞歸法

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

方法2：按規律取n階次方

【運作時間：11ms  占用記憶體：8280k】

public class Solution {
    public int JumpFloorII(int target) {
        if(target==0)	return 0;
        int result=(int)Math.pow(2,target-1);
        return result;
    }
}
           

方法3：動态規劃

【運作時間：12ms  占用記憶體：8272k】

public class Solution {
    public int JumpFloorII(int target) {
        if(target==0||target==1)	return 1;
        int dp0=1;
        int result=0;
        for(int i=2;i<=target;i++){
            result=2*dp0;
            dp0=result;
        }
        return result;
    }
}