파비의 매일매일 공부기록

Today's Challenge 본문

Problem Solving/LeetCode

Today's Challenge

fabichoi 2022. 12. 24. 23:45

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

 

Domino and Tromino Tiling - LeetCode

Domino and Tromino Tiling - You have two types of tiles: a 2 x 1 domino shape and a tromino shape. You may rotate these shapes. [https://assets.leetcode.com/uploads/2021/07/15/lc-domino.jpg] Given an integer n, return the number of ways to tile an 2 x n bo

leetcode.com

전형적인 DP 문제.
두개짜리 블럭과 세개짜리 불럭을 적절히 조합하면 될 듯.
결국은 점화식 문제

class Solution:
    def numTilings(self, n: int) -> int:
        a = [0] * (n+1)
        b = [1, 1] + [0] * (n-1)

        for i in range(2, n+1):
            a[i] = (b[i-2] + a[i-1]) % int(1e9 + 7)
            b[i] = (b[i-1] + b[i-2] + a[i-1] * 2) % int(1e9 + 7)
        return b[n]
반응형

'Problem Solving > LeetCode' 카테고리의 다른 글

Today's Challenge  (0) 2022.12.26
Today's Challenge  (0) 2022.12.25
Today's Challenge  (0) 2022.12.23
Today's Challenge  (0) 2022.12.22
Today's Challenge  (0) 2022.12.21
'Problem Solving/LeetCode' Related Articles more
Comments