DP--爬樓梯1

題目描述

前幾個月放映的頭号玩家簡直火得不能再火了，作為一個探索終極AI的研究人員，月神自然去看了此神劇。

由于太過興奮，晚上月神做了一個奇怪的夢，月神夢見自己掉入了一個被施放了魔法的深淵，月神想要爬上此深淵。

已知深淵有N層台階構成（1 <= N <= 1000)，并且每次月神僅可往上爬2的整數次幂個台階(1、2、4、....)，請你程式設計告訴月神，月神有多少種方法爬出深淵

輸入描述:

輸入共有M行，(1<=M<=1000)

第一行輸入一個數M表示有多少組測試資料，

接着有M行，每一行都輸入一個N表示深淵的台階數

輸出描述:

輸出可能的爬出深淵的方式

示例1

輸入

複制

4

1

2

3

4

輸出

複制

1

2

3

6

備注:

#include<iostream>
#include<vector>
using namespace std;

int main(){
    int M;int N;long Mod = 1000000003;
    scanf("%d",&M);
    vector<int> Vec(10);
    for(int i = 0;i < 10;i ++){
        int m = 1 << i;
        Vec[i] = m;
    }
    for(int j = 0;j < M;j ++){
        scanf("%d",&N);
        vector<int> dp(1001,0);
        dp[0] = 1;
        for(int i = 1;i <= N;i ++){
            for(auto v : Vec){
                if(v <= i){
                    dp[i] += dp[i - v];
                    dp[i] = dp[i] % Mod;
                }
            }
        }
        printf("%d\n",dp[N]);
    }
    return 0;
}