[c언어/c++] 타일링 2 - TILING 2 동적계획법

2xn 크기의 사각형을 2x1 크기의 사각형으로 빈틈없이 채우는 경우의 수를 구하는 프로그램을 작성하세요.

예를 들어 n=5라고 하면 다음 그림과 같이 여덟 가지의 방법이 있습니다.

경우의 수는 n이 커지면 아주 커질 수 있으므로, 1000000007으로 나눈 값을 대신 출력하세요.

문제 전체 링크 - https://algospot.com/judge/problem/read/TILING2 

#include<stdio.h>
#include<algorithm>
#include<memory.h>
using namespace std;

int n;
int cache[100];

long tile(int);

int main(){
 int c;
 scanf(" %d",&c);

 for(int loop = 0 ; loop < c ; loop++){
  memset(cache,-1,sizeof(cache));
  scanf(" %d",&n);
  printf("%d\n",tile(0));
 }
 return 0;
}
long tile(int index){
 if(index == n) return 1;
 if(index > n) return 0;
 if(cache[index] != -1) return cache[index];
 return cache[index] = (tile(index+1) + tile(index+2))%1000000007;

}