790. Domino and Tromino Tiling

790. Domino and Tromino Tiling

https://leetcode.com/problems/domino-and-tromino-tiling/

문제

풀이(처음 푼 풀이)

n = 1일 때 => 1
n = 2일 때 => 2
n = 3일 때 => (dp[2] + dp[1]) + 2 = 5
n = 4일 때 => (dp[3] + dp[2]) + 2(dp[1]) + 2 = 7 + 2 + 2 = 11
n = 5일 때 => (dp[4] + dp[3]) + 2(dp[2] + dp[1]) + 2 = 16 + 6 + 2 = 24
즉 i = n일 때 다음과 같이 점화식을 세울 수 있다.
dp[n] = (dp[n-1] + dp[n-2]) + 2*(dp[n-3] + ..... + dp[1]) + 2
점화식을 토대로 코드화 하면 다음과 같다.

결과