2698 인접한 비트의 개수

https://www.acmicpc.net/problem/2698

D[N][K][L] = 길이가 N이고 인접한 비트의 개수가 K개이면서 마지막 비트가 L인 수열의 개수라고 정의하자. 마지막 부분의 이전 상태와의 비교를 통해 점화식을 유도한다.

1. 마지막 비트가 0인 경우 이전 비트가 무엇이든 인접한 비트의 개수에 영향을 주지 않는다.

D[N][K][0]=D[N-1][K][0]+D[N-1][K][1]

2. 마지막 비트가 1인 경우 이전 비트가 1이면 인접한 비트의 개수가 하나 추가된다.

D[N][K][1]=D[N-1][K][0]+D[N-1][K-1][1]

#include <cstdio>
 
int t,a,b,d[101][101][2];
 
int main()
{
    d[1][0][0]=d[1][0][1]=1;
    for(int i=2;i<=100;i++)
    {
        for(int j=0;j<=i-1;j++)
        {
            d[i][j][0]=d[i-1][j][0]+d[i-1][j][1];
            d[i][j][1]=d[i-1][j][0]+d[i-1][j-1][1];
        }
    }
    scanf("%d",&t);
    while(t--)
    {
        scanf("%d %d",&a,&b);
        printf("%d\n",d[a][b][0]+d[a][b][1]);
    }
    return 0;
}