Ways To Tile A Floor

JavaView on GFG

Time: O(n)

Space: O(1)

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?