Ways to Tile the Floor

Time: O(n)

Space: O(n)

Problem Overview

Tile an n × m floor with unlimited 1 × m tiles placed horizontally (one full row) or vertically (m rows × one column).

Intuition

Tile an n × m floor with unlimited 1 × m tiles placed horizontally (one full row) or vertically (m rows × one column). When fewer than m rows remain, only horizontal rows work (one layout). At exactly m rows, choose all-horizontal or all-vertical (two layouts). Beyond that, either add one horizontal row to a smaller board or stack a vertical block of height m.

Algorithm

1dp[i] = ways to tile first i rows.
2If i < m: dp[i] = 1 (horizontal rows only).
3If i = m: dp[i] = 2 (all horizontal or all vertical).
4If i > m: dp[i] = (dp[i − 1] + dp[i − m]) mod 10⁹ + 7.
5Return dp[n].

Example Walkthrough

Input: n = 4, m = 4

1. dp[1..3] = 1. dp[4] = dp[3] + dp[0] = 2 (four horizontals or four verticals).

Output: 2

Common Pitfalls

• Not the same as 2 × N domino tiling — tile length equals full row width m.
• Vertical placement needs n ≥ m; for n = 2, m = 3 only horizontals fit.
• Apply modulo on every addition for large n.

Ways to Tile the Floor.java

Java

// Approach: Process rows top to bottom. If i < m, only horizontal tiles fit (one way).
// At i = m: all-horizontal or all-vertical gives 2 ways. For i > m: extend with one
// horizontal row (dp[i-1]) or add a vertical strip block of height m (dp[i-m]).
// Time: O(n) Space: O(n)

class Solution {

    public int countWays(int n, int m) {
        int mod = 1_000_000_007;
        int[] dp = new int[n + 1];

        for (int i = 1; i <= n; i++) {
            if (i > m) {
                dp[i] = (dp[i - 1] + dp[i - m]) % mod;
            } else if (i < m) {
                dp[i] = 1;
            } else {
                dp[i] = 2;
            }
        }

        return dp[n];
    }
}

Was this solution helpful?