题目难度：二星
考察点：动态规划、预处理

方法1：暴力、动态规划

  1. 分析：

这个题很像之前的跳台阶：一共有n个台阶，青蛙只能跳1阶或者是2阶，问有多少种跳法？
跳台阶思路如下:
假设青蛙跳n个台阶的跳法为f(n)那么：
如果第一次跳的是1阶，那么剩下的n-1个台阶，跳法是f(n-1)
如果第一次跳的是2阶，那么剩下的n-2个台阶，跳法是f(n-2)
由此可得：f(n) = f(n-1) + f(n-2)
当n=1时，f(1) = 1
当n=2时，f(2) = 2
至此，跳台阶问题已经解决。
对于这道题来说的话，我们可以借助之前的想法，假设月神有f(n)种方法能够跳出深渊，那么就有：
如果第一次跳的是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=0时，f(0) = 1。

算法实现：
(1). 用一个数组p表示2的幂，其中p[i]=2^i
(2). 输入n，然后从1遍历到n，在来一个内层循环j表示2^j，然后如果i >= p[j]， dp[i] += dp[i-p[j]]，不要忘记取模
(2). 输出结果dp[n]。

2. 复杂度分析：

时间复杂度：O(n^2log(n))
空间复杂度：O(n)


3. 代码： 

#include 
using namespace std;
typedef long long LL;
int p[10] = {1, 2, 4, 8, 16, 32, 64, 128, 256, 512};
const int MAXN = 1e3+5;
const int MOD = 1e9+3;
LL dp[MAXN];
int main() {
 int m; cin>>m;
 while(m--) {
     int n; cin>>n;
     memset(dp, 0, sizeof dp);
     dp[0] = 1;
     for(int i=1; i<=n; i++) {
         for(int j=0; j<10; j++) {
             if(i < p[j]) break;
             dp[i] = (dp[i] + dp[i-p[j]]) % MOD;
         }
     }
     cout<<dp[n]<<endl;
 }
 return 0;
}

方法2：预处理、动态规划


  1. 分析：

    其实在上述的代码中，我们其实没有必要在m层循环中，每次都计算一遍dp[n]，这样是浪费时间的，我们可以提前预处理一下dp[n]的计算方法，这样在循环中只需要输入一个n，输出一个dp[n]即可，具体详见代码。


  2. 复杂度分析：

    时间复杂度：O(max(nlog(n), m))
    空间复杂度：O(n)

  3. 代码： 

    #include 
using namespace std;
typedef long long LL;
int p[10] = {1, 2, 4, 8, 16, 32, 64, 128, 256, 512};
const int MAXN = 1e3+5;
const int MOD = 1e9+3;
LL dp[MAXN];
void Init() {
 dp[0] = 1;
 for(int i=1; i<MAXN; i++) {
     for(int j=0; j<10; j++) {
         if(i < p[j]) break;
         dp[i] = (dp[i] + dp[i-p[j]]) % MOD;
     }
 }
}
int main() {
 int m; cin>>m;
 Init();
 while(m--) {
     int n; cin>>n;
     cout<<dp[n]<<endl;
 }
 return 0;
}