[동적계획법]비트 스트링

Q. 0,1로 구성된 길이 n의 비트 스트링 가준데 1이 연속하지 않는 비트 스트링의 갯수는?

1. C(n) : 길이 n인 비트 스트링에서 1이 연속하지 않을 경우의 수
2. C(i) : 0<= i <= n
3. 기저 조건
   C(1) = 2  (  0 , 1 하나씩 경우 2개 )
   C(2) = 3 ( 00, 01, 10 )
4. 재귀식(거꾸로, case를 나눠서)
   C(i) 에서 마지막 자리가 0 이라면,
   => C(i-1)의 비트스트링에 0을 추가
   C(i) 에서 마지막 자리가 1이라면
   => C(i-2)에 0을 먼저 추가하고 1을 추가

   C(i) = C(i-1) + C(i-2)

   결국 1이 연속하지 않을 경우는 C(i-1)에 0을 추가한것과 C(i-2)에 01을 추가한 경우

5. 코딩 생략… 사다리 타기와 같음