Ways To Tile A Floor

JavaView on GFG

Time: O(n)

Space: O(1)

Problem Overview

Count ways to tile 2xN floor with 1x2 tiles.

See our study guide for structured GFG and LeetCode practice.

Intuition

Count ways to tile 2xN floor with 1x2 tiles. Classic DP: dp[n] = dp[n-1] + dp[n-2] (Fibonacci-like).

Algorithm

1dp[0]=1, dp[1]=1. dp[n] = dp[n-1] + dp[n-2].

Common Pitfalls

• Tile horizontally (1 way for last 2 cols) or vertically (1 way for last col). Fibonacci recurrence.

Ways To Tile A Floor.java

Java

// Approach: DP. dp[i] = ways to tile floor of width i. dp[i] = dp[i-1] (1-tile) + dp[i-2] (2-tile).
// Time: O(n) Space: O(1)
import java.util.*;

class Solution {
    public int numberOfWays(int n) {
        Map<Integer, Integer> hm = new HashMap<>();

        return find(hm, n);
    }

    private int find(Map<Integer, Integer> hm, int n) {
        if (n == 0)
            return 1;
        if (n < 0)
            return 0;
        if (hm.containsKey(n))
            return hm.get(n);

        int ans = find(hm, n - 1) + find(hm, n - 2);
        hm.put(n, ans);

        return ans;
    }
};

Was this solution helpful?