Count Number of Ways to Place Houses
You can solve this problem by using dynamic programming. The idea is to consider the possible placements for each plot and combine the solutions to find the overall answer.
Python Solution:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
| class Solution:
def countHousePlacements(self, n: int) -> int:
MOD = 10**9 + 7
# dp[i] represents the number of ways to place houses on i plots on one side of the street
dp = [0] * (n + 1)
dp[0] = 1 # 1 way to place houses on 0 plots (leave them empty)
dp[1] = 2 # 2 ways to place houses on 1 plot (leave it empty or place a house)
for i in range(2, n + 1):
# Either place a house on the current plot and leave the previous one empty
# or leave the current plot empty and consider the previous one
dp[i] = (dp[i - 1] + dp[i - 2]) % MOD
# The total number of ways for both sides of the street
total_ways = (dp[n] * dp[n]) % MOD
return total_ways
|
This code first calculates the number of ways to place houses on one side of the street, and then squares that number to find the overall solution. It also uses the modulo operator to ensure that the result fits within the required bounds.