#2320
Count Number of Ways to Place Houses
specialist · 985 · lc medium +32 · verified · 43.8% accepted · 644 likes · top 25%
Description
A street has n * 2 plots — n on each side — numbered 1 to n. A house may be placed on any plot.
Return the number of distinct placement arrangements such that no two adjacent plots on the same side both have houses. Because the answer may be very large, return it modulo 109 + 7.
Note: plots on opposite sides of the street at the same position are independent — both may have houses.
Example 1:
Input: n = 1
Output: 4
Explanation:
Possible arrangements:
1. All plots are empty.
2. A house is placed on one side of the street.
3. A house is placed on the other side of the street.
4. Two houses are placed, one on each side of the street.
Example 2:
Input: n = 2
Output: 9
Explanation: The 9 possible arrangements are shown in the diagram above.
Code
1
2
3