What Is 2-by-n Tiling?
2-by-n tiling asks: given a rectangular strip that is 2 cells wide and n cells long, how many ways can you fill it completely with 1x2 (horizontal) and 2x1 (vertical) tiles, with no gaps and no overlaps?
It's one of the most intuitive first examples of Dynamic Programming (DP). If you sketch a few solutions, you can literally see how the cases split cleanly based on "how you cover the last column."
Why Does It Matter?
- •Textbook recurrence design: It teaches the "reason about the last piece" technique.
- •Same structure as Fibonacci: dp[i]=dp[i-1]+dp[i-2], perfect for learning recurrences.
- •Common interview pattern: It's the foundation of tiling / grid-filling problems.
Building the Recurrence
Think about how to cover the last column of the strip.
Case 1. Cover the end with one vertical tile (2x1) -> a length i-1 strip remains -> dp[i-1] ways
Case 2. Cover the end with two horizontal tiles (1x2) stacked -> a length i-2 strip remains -> dp[i-2] ways
The two cases never overlap, so we add them.
dp[i] = dp[i-1] + dp[i-2]Base cases
- •dp[1] = 1 (one vertical)
- •dp[2] = 2 (two vertical / two horizontal)
Filling In the Values
| length i | 1 | 2 | 3 | 4 | 5 | 6 |
|---|---|---|---|---|---|---|
| dp[i] | 1 | 2 | 3 | 5 | 8 | 13 |
dp[3]=2+1=3, dp[4]=3+2=5, dp[5]=5+3=8, dp[6]=8+5=13 — exactly the Fibonacci sequence.
Time and Space Complexity
| Complexity | |
|---|---|
| Time | O(n) |
| Space (array) | O(n) |
| Space (two variables) | O(1) |
Each subproblem is computed once, so it's O(n). Keeping only the last two values lets you solve it in O(1) space without an array.
Common Mistakes
- •Wrong base cases: Set dp[1]=1 and dp[2]=2 precisely. Using dp[2]=1 throws everything off.
- •Misreading the tiles: Only two shapes, 1x2 and 2x1, with rotation allowed. Adding L-shapes makes it a different problem.
- •Redundant work: Pure recursion blows up to O(2^n). Always use memoization or bottom-up DP.
See It in Action on AlgoNote
Watch how dp[i] is built from dp[i-1] and dp[i-2] as the length grows, one step at a time, on AlgoNote.