algospot - tiling2

//algospot - tiling2
 
#include <iostream>
#include <vector>
using namespace std;
 
#define INF 1000000007
 
int N;
vector<int> cache;
 
void init()
{
    cin >> N;
    cache = vector<int>(N, -1);
}
 
int dp(int idx)
{
    if(idx == N)
        return 1;
    int& ret = cache[idx];
    if(ret != -1)
        return ret;
    ret = 0;
    if(idx + 1 <= N)
        ret += dp(idx+1);
    if(idx + 2 <= N)
        ret += dp(idx+2);
    ret %= INF;
    return ret;
}
 
int main()
{
    int C; cin >> C;
    for(int tn = 0; tn<C; ++tn)
    {
        init();
        cout << dp(0) << "\n";
    }
}

 

 

 

 

 

https://www.algospot.com/judge/problem/read/TILING2

algospot.com :: TILING2

 

 

 

 

 

TILING2

경우의수 DP문제