출처 : https://www.acmicpc.net/problem/2193
규칙 :
1. 처음시작은 무조건 1
2. 1 다음에 1이 올 수 없음
2. 0 다음엔 0, 1 둘다 올 수 있음
점화식 :
D[n] = D[n][0] + D[i, j][1]
D[n][0] = D[n-1][0] + D[n-1][1] // n자리일때 끝이 0으로 끝날 수 있는 경우는 n-1자리일때 0, 1로 끝나는 경우의 수의 합
D[n][1] = D[n-1][0] // n자리일때 끝이 1로 끝날 수 있는 경우는 n-1자리일때 1로 끝나는 경우의 수
정리 -> D[n] = D[n-1][0] * 2 + D[n-1][1]