73th LeetCode Weekly Contest Domino and Tromino Tiling
We have two types of tiles: a 2x1 domino shape, and an "L" tromino shape. These shapes may be rotated.
XX <- domino XX <- "L" tromino
X
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: 3
Output: 5
Explanation:
The five different ways are listed below, different letters indicates different tiles:
XYZ XXZ XYY XXY XYY
XYZ YYZ XZZ XYY XXY
Note:
- N will be in range
[1, 1000]
.
一块区域有--,L(上下两种位置),问2*N有几种放置方式。
首先
x 这种我们叫0
x
x这种我们叫1
xx
xx这种我们叫2
x
xxx是怎么得到的呢。一种是x+横着和竖着 xx+竖着 xx+L形(上下两种)
xxx x xx x
于是...dp[i][0]=dp[i-2][0]+dp[i-1][0]+dp[i-1][1]+dp[i-1][2] i表示列数啦
xxxx是怎么得到的呢。xx+L xx+ --
xxx xx xxx
dp[i][1]=dp[i-2][0]+dp[i-1][2]
xxx同理
xxxx
class Solution {
public:
const int mod = ;
int dp[][];
int numTilings(int N) {
dp[][]=,dp[][]=;
for(int i=;i<=N;i++){
dp[i][]=(dp[i-][]%mod+dp[i-][]%mod)%mod+(dp[i-][]%mod+dp[i-][]%mod)%mod;
dp[i][]=(dp[i-][]%mod+dp[i-][]%mod)%mod;
dp[i][]=(dp[i-][]%mod+dp[i-][]%mod)%mod;
}
return dp[N][]%mod;
}
};
最新文章
- 两种方式testng dataprovider结合csv做测试驱动
- android图片透明度跟缩放大小动画事件
- IDEA建立---- java web项目
- js 漩涡
- iptables禁止端口和开放端口
- Eclipse改变外观,护眼模式
- Http请求 post get
- ADS-B 雷达 显示终端5.8
- elk5.4小白踩坑记录
- Servlet之Request对象
- 论JavaScript的作用域
- linux同步Internet时间
- css td hover 选择器无效
- 给 Chrome浏览器 添加 Javascript小书签,查看当前页面全部加载的javascript文件及代码片段
- Linux运维故障排查思路
- Hbase记录-HBase客户端API
- update更新另一个字段
- 使用postman模拟appium的http请求
- (快速幂)Key Set--hdu--5363
- C#委托和事件的使用的意义