魔法深渊

题1：一只青蛙一次可以跳上1级台阶，也可以跳上2级。（排列问题，先后次序不同算不同的结果）
青蛙的第一跳有两种情况，跳一阶和跳二阶。如果跳一阶，则剩下n-1阶就是f(n-1)中跳法；如果挑两阶，则剩下n-2阶就是f(n-2)种情况。所以总情况就是f(n)=f(n-1)+f(n-2);即斐波那契数列。

题2(变态跳台阶)：一只青蛙一次可以跳上1级台阶，也可以跳上2级……它也可以跳上n级。
因为n级台阶，第一步有n种跳法：跳1级、跳2级、到跳n级
跳1级，剩下n-1级，则剩下跳法是f(n-1)
跳2级，剩下n-2级，则剩下跳法是f(n-2)
所以f(n)=f(n-1)+f(n-2)+...+f(1)
那么f(n-1)=f(n-2)+f(n-3)+...+f(1)
通项f(n-1)可得
f(n)=2*f(n-1)
输出结果:console.log(2**(n-1))\

题3(月神跳台阶)：
如果第一次跳的是2^0阶，那么剩下的n-2^0个台阶，就有f(n-2^0)种跳法。
如果第一次跳的是2^1阶，那么剩下的n-2^1个台阶，就有f(n-2^1)种跳法。
...
如果第一次跳的是2^k阶，那么剩下的n-2^k个台阶，就有f(n-2^k)种跳法。
其中k为不超过n的2的次幂的指数最大值。
根据通项式：f(n) = f(n-2^0) + f(n-2^1) + ... + f(n-2^k), n >= 2^k;
以F(15)为例，15二进制表示为1111
(15).toString(2).length => 4。
2^(4-1)<15成立
二进制长度即为m。m用来控制循环次数,从(m-1)到0一共m次。\

 while(n = readline()){
     console.log(jump(n))
 }

输入的不是数字是字符串。。。字符串在(4).toString(2).length这里得到的是'4'.length => 1。加上parseInt()就好了。\

 while(n = readline()){
     console.log(jump(parseInt(n)))
 }

完整代码：

readline()
var arr = [1,1,2,3]
let MOD = 1e9+3
function jump(num){
    if(arr[num])return arr[num]
    let len = num.toString(2).length;
    let res = 0;
    while(len--){
        res += jump(num-2**len)
    }
    return arr[num]= res % MOD
}
while(n = readline()){
    print(jump(parseInt(n)))
}

既然用数组缓存每个"状态"了，那直接用数组下标
arr[n] = arr[n - 2^0] + arr[n - 2^1] + ... + arr[n - 2^m]
替代递归函数下标
f(n) = f(n -2^0) + f(n - 2^1) + ... + f(n - 2^m)
去考虑，所以有迭代版本：

let n = readline()
let arr = []
let mod = 1e9+3
for(let i = 0; i < n; i++){
arr.push(parseInt(readline()))
}
let dp = [1,1,2,3]
for(let i = 4; i <= arr[n-1]; i++){
    let temp = i.toString(2).length;
    while (temp--) {
        dp[i] = dp[i] || 0;
        dp[i] += dp[i - 2**temp];
        dp[i] = dp[i] % mod;
    }
}

arr.forEach(e => print(dp[e]))