안녕하세요.

1년전에 질문하신거면 지금쯤 답을 찾으셨으리라 생각합니다.

저도 질문자님처럼 그 부분을 몰라서 직접 손으로 과정을 따라가면서 생각해보니 이해가 됫네요 ㅎㅎ

혹시 질문자님이나 저처럼 고민하신분들의 소중한 시간을 위해 최대한 이해가능하게 설명 남기겠습니다.

점화식의 함수를 tiling이라 치환하여 설명하겠습니다.

tiling(5) 를 예시로 보이겠습와니다.

tiling(5) = 2 * tiling(5-1) + 3 * tiling(5-2) + 2(tiling(5-3) + tiling(5-5)) 

                    2 * tiling(4) + 3 tiling(3) + 2 ( tiling(2) +tiling (1) + tiling (0) )

이렇게 됩니다.

여기서  표로 보게 되면 이런 모양이 됩니다.

DP             0               1                 2               3                             4                                      5

DP[][0]      1                2                7               22                           71

DP[][1]                                                           1                      1      +     2                        1      +     2       +     7
                                                                tiling(0)            tiling(0) + tiling(1)             tiling(0) + tiling(1) + tiling(2)         tiling(2) == DP[x-3][0]

이처럼 2차원 배열에서는 2 * DP[x-2][0]와 3 * DP[x-1][0]을 제외한 특수한 경우의 수를 보관해야합니다.

그런데 DP[x-1][1]에서는 DP[x-3][0] 이후의 케이스들만 담고 있기 때문에 DP[x-3][0]의 케이스를 더해야 합니다.

제가 설명을 잘못해서 최대한 이해될 수 있는 요소들을 추가 했는데 이해 안되면 tiling(6)의 케이스를 직접 손으로 풀어보시길 바랍니다.