790. Domino and Tromino Tiling

Leetcode link

题目简介

/**
 * @param {number} n
 * @return {number}
 */

题目给我们两种方块：domino shape、tromino shape

要求我们用这两个方块放进 2*n 的格子里

我们需要返回总共有多少种放进去的选择

解题思路

Javascript

/**
 * @param {number} n
 * @return {number}
 */
var numTilings = function (n) {
    const MOD = Math.pow(10, 9) + 7
    const dp = [1, 1, 2, 5]

    for (let i = 4; i <= n; i++) {
        dp[i] = (dp[i - 1] * 2 + dp[i - 3]) % MOD
    }

    return dp[n]
};

复杂度分析

时间

O(n)

空间

O(n)