Count Number of Ways to Place Houses

medium dp

Problem

There is a street with n plots on each side of the road. On each side, you may build houses such that no two houses are on adjacent plots. The two sides are independent. Return the number of ways to place houses, modulo 10^9 + 7.

Inputn = 3

Output25

One side has f(3) = 5 valid arrangements (Fibonacci). Two independent sides give 5 × 5 = 25.

def count_houses_placements(n):
    MOD = 10**9 + 7
    # f[k] = ways to fill k plots on one side (no two adjacent)
    f = [0] * (n + 1)
    f[0] = 1
    f[1] = 2
    for k in range(2, n + 1):
        f[k] = (f[k - 1] + f[k - 2]) % MOD
    return (f[n] * f[n]) % MOD

function countHousePlacements(n) {
  const MOD = 1000000007n;
  const f = new Array(n + 1).fill(0n);
  f[0] = 1n;
  if (n >= 1) f[1] = 2n;
  for (let k = 2; k <= n; k++) {
    f[k] = (f[k - 1] + f[k - 2]) % MOD;
  }
  return Number((f[n] * f[n]) % MOD);
}

class Solution {
    public int countHousePlacements(int n) {
        long MOD = 1_000_000_007L;
        long[] f = new long[n + 1];
        f[0] = 1;
        if (n >= 1) f[1] = 2;
        for (int k = 2; k <= n; k++) {
            f[k] = (f[k - 1] + f[k - 2]) % MOD;
        }
        return (int)((f[n] * f[n]) % MOD);
    }
}

int countHousePlacements(int n) {
    const long long MOD = 1000000007LL;
    vector<long long> f(n + 1, 0);
    f[0] = 1;
    if (n >= 1) f[1] = 2;
    for (int k = 2; k <= n; k++) {
        f[k] = (f[k - 1] + f[k - 2]) % MOD;
    }
    return (int)((f[n] * f[n]) % MOD);
}

Explanation

The two sides of the road never interact, so if one side has x valid arrangements, the whole street has x × x arrangements. The job reduces to counting placements on a single row of n plots where no two houses touch.

Let f[k] be the number of valid ways to fill the first k plots. Consider the last plot: either it is empty (then the first k-1 plots can be anything valid → f[k-1] ways), or it has a house (then plot k-1 must be empty, leaving f[k-2] ways). So f[k] = f[k-1] + f[k-2] — the Fibonacci recurrence.

The base cases are f[0] = 1 (one way to fill zero plots: build nothing) and f[1] = 2 (the single plot is either empty or has a house).

Because the values grow fast, every addition is taken modulo 10^9 + 7. The final answer squares f[n] for the two independent sides, again under the modulus.

Example: n = 3. We get f = [1, 2, 3, 5], so one side has 5 layouts and the street has 5 × 5 = 25.

Time: O(n) Space: O(n)