인접한 비트의 개수

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

풀이

• 어렵다

• d[i][j][m]

    길이가 i인 수열, 
  

  ​ 인접 비트 개수가 j,
  ​ 마지막 비트가 m인 ( m : 0 or 1 )
  ​ 수열의 경우의 수

• 마지막 비트가 0

  • 이전 비트가 0 : 경우의 수에 영향 X
  • 이전 비트가 1 : 경우의 수에 영향 X

• 마지막 비트가 1

  • 이전 비트가 0 : 경우의 수에 영향 X
  • 이전 비트가 1 : 경우의 수에 영향 O