initial
I solved exactly same problem in baekjoon. It is just identifying pattern of dp[n] = dp[n-1]*2+dp[n-3].
class Solution:
def numTilings(self, n: int) -> int:
dp=[0 for _ in range(1001)]
dp[1]=1
dp[2]=2
dp[3]=5
for i in range(4,n+1):
dp[i]=(dp[i-1]*2+dp[i-3])%(10**9+7)
return dp[n]sol
But this https://leetcode.com/problems/domino-and-tromino-tiling/solutions/116581/detail-and-explanation-of-o-n-solution-why-dp-n-2-d-n-1-dp-n-3/?envType=daily-question&envId=2025-05-05
solution explains well the pattern.
From dp[n-1] to form dp[n], there is only 1 option to add | (1 vertical stick). From dp[n-2] to for dp[n], we can add either || or = but this || option has already been explored by dp[n-1] so we only can use this = option so 1 choice. From d[n-3] onwards, we have 2 options (traingle ones).
So general formula is
dp[n] = dp[n-1] + dp[n-2] + 2 (dp[n-3] + ... + dp[0]) -- E1
dp[n-1] = dp[n-2] + dp[n-3] + 2 (dp[n-4] + ... + dp[0]) -- E2
.
.
E1 - E2:
dp[n] - dp[n-1] = dp[n-1] + dp[n-3]
--> dp[n] = 2*dp[n-1] + dp[n-3]
complexity
n time
n space
