标签: 动态规划
难度: Medium
一条街道上共有 n * 2 个 地块 ，街道的两侧各有 n 个地块。每一边的地块都按从 1 到 n 编号。每个地块上都可以放置一所房子。
现要求街道同一侧不能存在两所房子相邻的情况，请你计算并返回放置房屋的方式数目。由于答案可能很大，需要对 109 + 7 取余后再返回。
注意，如果一所房子放置在这条街某一侧上的第 i 个地块，不影响在另一侧的第 i 个地块放置房子。
示例 1：
输入：n = 1 输出：4 解释： 可能的放置方式： 1. 所有地块都不放置房子。 2. 一所房子放在街道的某一侧。 3. 一所房子放在街道的另一侧。 4. 放置两所房子，街道两侧各放置一所。
示例 2：
输入：n = 2 输出：9 解释：如上图所示，共有 9 种可能的放置方式。
提示：
1 <= n <= 104运行时间: 35 ms
内存: 16.3 MB
MOD = 10 ** 9 + 7
f = [1, 2] #空 放与不放
for _ in range(10 ** 4 - 1):
f.append((f[-1] + f[-2]) % MOD)
class Solution:
def countHousePlacements(self, n: int) -> int:
return f[n] ** 2 % MOD
这个问题可以通过动态规划来解决。考虑一条街道的一侧，我们需要计算不相邻放置房子的方式数。定义f[i]为长度为i的街道，放置房子的方式数。对于第i个地块，我们有两种选择：1) 不放置房子，此时问题变为计算f[i-1]；2) 放置房子，此时第i-1个地块一定不能放置房子，所以问题变为计算f[i-2]。因此，状态转移方程为f[i] = f[i-1] + f[i-2]，这与斐波那契数列相同。初始化条件是f[0]=1（没有地块时，只有一种放置方式，即不放置）和f[1]=2（一个地块时，放置和不放置两种方式）。这个动态规划只需要处理到f[n]即可。由于两侧的街道是独立的，最终答案为f[n]的平方，然后对MOD取余。
时间复杂度: O(n)
空间复杂度: O(n)
# 预先计算斐波那契数列，模10^9+7
MOD = 10 ** 9 + 7
f = [1, 2] # f[0]表示没有地块时的放置方式数，f[1]表示有1个地块时的放置方式数
for _ in range(10 ** 4 - 1):
f.append((f[-1] + f[-2]) % MOD) # 根据递推公式计算f[i]
class Solution:
def countHousePlacements(self, n: int) -> int:
# 计算两侧街道的放置方式数的平方，然后取模
return f[n] ** 2 % MOD
这个问题可以被简化为计算单边街道的放置方式，因为街道的两边是独立的，放置在一边的房子不会影响另一边的放置方式。因此，计算一边街道的所有放置方式后，另一边街道同样有相同数量的放置方式。最终的放置组合数为一边的方式数与另一边方式数的乘积，即单边放置方式数的平方。
在该问题中，我们的主要约束是不能在相邻的地块上放置房子。因此，如果在第i个地块上放置房子，第i-1个地块就不能放置房子，这使得问题的子问题变为考虑到第i-2个地块的所有可能放置方式。由于更远的地块（如第i-3个）与第i个地块之间的放置独立，不会直接影响第i个地块的放置决定，所以只需考虑到第i-2个地块的情况。这样，状态转移方程仅依赖f[i-1]和f[i-2]是合理的。
初始化条件中，f[0]=1表示在没有地块的情况下，只有一种'放置'方式，即什么都不做。这是因为没有空间放置任何房子。而f[1]=2代表有一个地块时，存在两种可能：放置一个房子或者不放置。因此，对于一个地块，我们可以选择放置房子（一种方式）或不放置（另一种方式），总共有两种方式。
因为街道两侧的放置是完全独立的，每边的放置方式都是f[n]种。因此，总的放置组合是这两边可能的放置方式的笛卡尔积，即每边的每一种放置方式都可以与另一边的任何一种方式组合。这使得总的组合方式数为f[n]的放置方式与f[n]的放置方式的乘积，即f[n]的平方。这保证了不会遗漏任何可能的放置方式组合。