Участник:Krivosheev.ah/domino-and-tromino-tiling

Материал из DISCOPAL
Перейти к: навигация, поиск

Python3

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

class Solution:
    def numTilings(self, N: int) -> int:
        dp = [1,1,2]
        M = 10**9 + 7
        if N <= 2:
            return dp[N]
        dp = dp + (N-2)*[0]
        for i in range(3, N+1):
            dp[i] = (2*dp[i-1] + dp[i-3]) % M
        return dp[-1]