[leetcode] 790. Domino and Tromino Tiling

[leetcode] 790. Domino and Tromino Tiling

Description

We have two types of tiles: a 2x1 domino shape, and an “L” tromino shape. These shapes may be rotated.

XX <- dominoXX <- "L" trominoX

Given N, how many ways are there to tile a 2 x N board? Return your answer modulo 10^9 + 7.

(In a tiling, every square must be covered by a tile. Two tilings are different if and only if there are two 4-directionally adjacent cells on the board such that exactly one of the tilings has both squares occupied by a tile.)

Example:Input: 3Output: 5Explanation: The five different ways are listed below, different letters indicates different tiles:XYZ XXZ XYY XXY XYYXYZ YYZ XZZ XYY XXY

Note:

N will be in range [1, 1000].

分析

题目的意思是：说是有一个2xN大小的棋盘，我们需要用这些多米诺和三格骨牌来将棋盘填满，问有多少种不同的填充方法，结果需要对一个超大数取余。

这道题我开始并没有看懂题目的意思，后面发现这个dp的推导过程也是奇葩，我也做不出来，学习一下。 dp[n] = dp[n-1] + dp[n-2] + 2 * (dp[n-3] + … + dp[0]) dp[n-1] = dp[n-2] + dp[n-3]+ 2 * (dp[n-4] + … dp[0]) 联立方程得： dp[n]-dp[n-1] = dp[n-3] + dp[n-1] dp[n]= 2 * dp[n-1] + dp[n-3]

代码

class Solution {public: int numTilings(int N) { int M=1e9+7; vector dp(N+1); dp[0]=1; dp[1]=1; dp[2]=2; for(int i=3;i<=N;i++){ dp[i]=(dp[i-1]*2+dp[i-3])%M; } return dp[N]; }};

参考文献

​​[LeetCode] Domino and Tromino Tiling 多米诺和三格骨牌​​

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。