5.19变态跳台阶 - WisperDin/blog GitHub Wiki

描述

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

分析

关键：跳n阶台阶问题其实包含了跳比n小的台阶的子问题

其实是斐波那契数列的变式问题，而且可以使用动态规划的思想优化

• 枚举 -- 以第一步的选择来枚举出每种台阶的跳法

当0阶的台阶时有1种跳法

当1阶的台阶时，只能先跳一步，又变成了0阶台阶问题，所以跳法为1

当2阶的台阶时，

• 一开始可以跳一步，是1阶台阶问题，此时跳法有1种
• 一开始可以跳两步，是0阶台阶的问题，此时跳法有1种

整理成式子

f(0)=1
f(1)=1
f(2)=f(2-1)+f(2-2)=f(1)+f(0)
f(3)=f(3-1)+f(3-2)+f(3-3)=f(2)+f(1)+f(0)
...

可以整理成

f(0)=1
f(1)=1
f(2)=f(1)+f(0)
f(3)=f(2)+f(2)=2*f(2)
...

所以通式

f(0)=1
f(1)=1
f(n)=f(n-1)*2 (n>=2)

实现

public class Solution {
    public int JumpFloorII(int target) {
        if(target<=1){
            return target;
        }
        int[] rec = new int[target+1];
        rec[0]=1;
        rec[1]=1;
        
        for(int i=2;i<=target;i++){
            rec[i] = rec[i-1]*2;
        }
        
        return rec[target];
    }
}