Problem statement

A floor is 2 units tall and n units wide. You have an unlimited supply of 2 x 1 tiles, and each tile may be placed either vertically (covering a 2 x 1 area) or horizontally (covering a 1 x 2 area).

Count the number of different ways to cover the whole floor with tiles, with no overlaps and nothing sticking out. Two tilings are different if some tile is placed differently.

The count grows exponentially, so return it modulo 10^9 + 7.

Example 1

Input: n = 3
Output: 3
Explanation: Three vertical tiles; or one vertical tile at the left and two stacked horizontal tiles; or two stacked horizontal tiles and then one vertical tile.

Example 2

Input: n = 4
Output: 5

Example 3

Input: n = 1
Output: 1
Explanation: A single vertical tile.

Constraints

• 1 <= n <= 10^5

Hints for Count Ways to Tile a 2 x N Floor

1. Hint 1

   Look at the left edge of the floor. How can the leftmost column be covered?

2. Hint 2

   Either one vertical tile covers it (leaving a 2 x (n - 1) floor), or two horizontal tiles stacked on top of each other cover the first two columns (leaving 2 x (n - 2)).

3. Hint 3

   So ways(n) = ways(n - 1) + ways(n - 2) with ways(0) = ways(1) = 1 — Fibonacci numbers. Iterate with two variables and reduce modulo 10^9 + 7.

How to solve Count Ways to Tile a 2 x N Floor

Classify tilings by what covers the leftmost column. A vertical tile there leaves a 2 x (n-1) floor; otherwise the top-left cell is covered by a horizontal tile, which forces another horizontal tile directly beneath it, leaving a 2 x (n-2) floor. The counts therefore follow the Fibonacci recurrence.

Approach

1. Let a = ways(0) = 1 and b = ways(1) = 1.
2. For i from 2 to n: c = (a + b) mod (10^9 + 7), then a = b, b = c.
3. Return b.

Why it works

The two cases are disjoint (the leftmost column holds either a vertical tile or two halves of horizontal tiles) and exhaustive. In the second case the bottom-left cell can only be covered by a horizontal tile too — a vertical one would overlap — so the first two columns are fully determined. Hence ways(n) = ways(n-1) + ways(n-2).

Complexity

• Time — O(n)
• Space — O(1)

Pitfalls

• Without the modulus the count overflows 32 bits already at n = 46.
• Recursion without memoisation is exponential, and with it the depth reaches 10^5 frames.
• In typed languages, add two residues in 64 bits or subtract the modulus — their sum can pass 2^31 - 1.

Reference solution

Python

def numberOfWays(n: int) -> int:
    MOD = 10**9 + 7
    a, b = 1, 1
    for _ in range(2, n + 1):
        a, b = b, (a + b) % MOD
    return b

Java

public static int numberOfWays(int n) {
    final long MOD = 1000000007L;
    long a = 1, b = 1;
    for (int i = 2; i <= n; i++) {
        long c = (a + b) % MOD;
        a = b;
        b = c;
    }
    return (int) b;
}

C++

int numberOfWays(int n) {
    const long long MOD = 1000000007LL;
    long long a = 1, b = 1;
    for (int i = 2; i <= n; i++) {
        long long c = (a + b) % MOD;
        a = b;
        b = c;
    }
    return (int) b;
}

JavaScript

var numberOfWays = function(n) {
    var MOD = 1000000007;
    var a = 1, b = 1;
    for (var i = 2; i <= n; i++) {
        var c = (a + b) % MOD;
        a = b;
        b = c;
    }
    return b;
};

Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.

More dynamic programming problems

• Multiply Two Linked Lists Easy
• Convert Binary Number in a Linked List to Integer Easy
• Check if Any Element Has Prime Frequency Easy
• Convert Date to Binary Easy
• Find Nth Root of M Easy
• Valid Boomerang Easy