A
A
Algorithm Practice
Search…
A
A
Algorithm Practice
Introduction
Lintcode
Leetcode
Math
Tree
Graph
Two Pointers
Linked List
Topological Sort
Hash Table
Trie
Sort
Binary Search
Heap
Breadth First Search
Stack
Backtracking
Dynamic Programming
LIS
Longest Common Subsequence
Interval DP
Knapsack Problem
10 Regular Expression Matching
32 Longest Valid Parentheses
44 Wildcard Matching
53 Maximum Subarray
62 Unique Paths
63 Unique Paths II
64 Minimum Path Sum
70 Climbing Stairs
85 Maximal Rectangle
87 Scramble String
91 Decode Ways
95 Unique Binary Search Trees II
96 Unique Binary Search Trees
97 Interleaving String
120 Triangle
121 Best Time to Buy and Sell Stock
122 Best Time to Buy and Sell Stock II
123 Best Time to Buy and Sell Stock III
139 Word Break
140 Word Break II
152 Maximum Product Subarray
174 Dungeon Game
188 Best Time to Buy and Sell Stock IV
198 House Robber
213 House Robber II
221 Maximal Square
238 Product of Array Except Self
256 Paint House
264 Ugly Number II
265 Paint House II
276 Paint Fence
279 Perfect Squares
303 Range Sum Query - Immutable
304 Range Sum Query 2D - Immutable
309 Best Time to Buy and Sell Stock with Cooldown
321 Create Maximum Number
338 Counting Bits
343 Integer Break
361 Bomb Enemy
363 Max Sum of Rectangle No Larger Than K
368 Largest Divisible Subset
403 Frog Jump
410 Split Array Largest Sum
413 Arithmetic Slices
418 Sentence Screen Fitting
446 Arithmetic Slices II - Subsequence
464 Can I Win
466 Count The Repetitions
467 Unique Substrings in Wraparound String
471 Encode String with Shortest Length
514 Freedom Trail
517 Super Washing Machines
523 Continuous Subarray Sum
552 Student Attendance Record II
562 Longest Line of Consecutive One in Matrix
568 Maximum Vacation Days
576 Out of Boundary Paths
600 Non-negative Integers without Consecutive Ones
629 K Inverse Pairs Array
638 Shopping Offers
639 Decode Ways II
650 2 Keys Keyboard
651 4 Keys Keyboard
656 Coin Path
688 Knight Probability in Chessboard
689 Maximum Sum of 3 Non-Overlapping Subarrays
691 Stickers to Spell Word
698 Partition to K Equal Sum Subsets
714 Best Time to Buy and Sell Stock with Transaction Fee
718 Maximum Length of Repeated Subarray
727 Minimum Window Subsequence
730 Count Different Palindromic Subsequences
740 Delete and Earn
741 Cherry Pickup
746 Min Cost Climbing Stairs
750 Number Of Corner Rectangles
764 Largest Plus Sign
787 Cheapest Flights Within K Stops
790 Domino and Tromino Tiling
801 Minimum Swaps To Make Sequences Increasing
Union Find
Scan Line
String
Reservoir Sampling
Recursion
Google
Powered By GitBook
790 Domino and Tromino Tiling

1. Question

We have two types of tiles: a 2x1 domino shape, and an "L" tromino shape. These shapes may be rotated.
1
XX <- domino
2
XX <- "L" tromino
3
X
Copied!
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.)
1
Example:
2
Input: 3
3
​
4
Output:5
5
​
6
Explanation:
7
​
8
The five different ways are listed below, different letters indicates different tiles:
9
XYZ XXZ XYY XXY XYY
10
XYZ YYZ XZZ XYY XXY
Copied!
Note:
  • N will be in range[1, 1000].

2. Implementation

(1) DP
思路: 从n = 1到n = 5先画出能拼出tile的，然后推导出递归公式。具体推导可以看这里。数学推导可以参考这个。
1
class Solution {
2
public int numTilings(int N) {
3
int MOD = 1000000007;
4
​
5
long[][] dp = new long[N + 1][3];
6
​
7
dp[0][0] = 1;
8
dp
9
[1][0] = 1;
10
​
11
for (int i = 2; i <= N; i++) {
12
dp[i][0] = (dp[i - 1][0] + dp[i - 2][0] + dp[i - 1][1] + dp[i - 1][2]) % MOD;
13
dp[i][1] = (dp[i - 2][0] + dp[i - 1][2]) % MOD;
14
dp[i][2] = (dp[i - 2][0] + dp[i - 1][1]) % MOD;
15
}
16
return (int)dp[N][0];
17
}
18
}
Copied!

3. Time & Space Complexity

DP:时间复杂度O(n), 空间复杂度O(n)
Previous
787 Cheapest Flights Within K Stops
Next
801 Minimum Swaps To Make Sequences Increasing
Last modified 2yr ago
Copy link
Contents
790. Domino and Tromino Tiling
1. Question
2. Implementation
3. Time & Space Complexity