Ebay test

Ebay 笔试题目，变态跳台阶的进阶版本

题目描述

有一只神奇的青蛙，擅长跳格子，而且她每次跳的格数都满足2^k(K>=0),现在这只青蛙站在第一个格子里，他如果要跳到第N个格子，一共有多少种不同的跳法呢？

例子 输入： 5
输出：6
代码如下,关键点都在下面

#include <iostream>
#include <math.h>
using namespace std;

int main(){
    int a[1000] = {0};//存储第n阶的可能次数
    a[1] = 1;
    int n; //台阶数
    cin>>n;
    if(n==1){
        cout<<1<<endl;
        return 0;
    }

    for(int i=1;i<=n;i++){
        int maxk=0;//算出每一个i所兼容的2的maxk次方
        for (int k = 0; k <i; ++k) {
            if(pow(2,k)>=n&&(k>maxk)){
                maxk=k-1;
                break;
            }
        }
        for(int j=1;j<=pow(2,maxk);j++){
            if(i-j>=0)// 递推计算，每次是前(2^maxk-1)个数相加
            {
                a[i] = a[i]+a[i-j];
            }
        }
    }
    cout<<a[n]<<endl;//输出n的结果
    return 0;
}