알고리즘/DP (1) 썸네일형 리스트형 [DP/ acmicpc] 이친수 출처 : https://www.acmicpc.net/problem/2193 규칙 : 1. 처음시작은 무조건 12. 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] 이전 1 다음