Medium

题目描述

有一条街道，街道两侧分别有 n 个地块，每侧的地块从 1 到 n 编号。每个地块上可以放置一栋房屋。

返回房屋放置的方式数，使得同一侧的街道上没有两栋房屋相邻。由于答案可能很大，返回对 10^9 + 7 取模的结果。

注意，如果在街道一侧的第 i 个地块上放置了房屋，那么在街道另一侧的第 i 个地块上也可以放置房屋。

示例 1：

输入：n = 1
输出：4
解释：
可能的排列：
1. 所有地块都是空的。
2. 在街道一侧放置一栋房屋。
3. 在街道另一侧放置一栋房屋。
4. 在街道两侧各放置一栋房屋。

示例 2：

输入：n = 2
输出：9
解释：如上图所示，共有 9 种可能的排列。

提示：

  • 1 <= n <= 10^4

解题思路

这道题需要分步骤思考：

  1. 单侧街道的动态规划：首先考虑街道一侧有 n 个地块的情况。定义 dp[i] 为前 i 个地块的合法放置方案数。每个地块有两种状态：放房屋或不放房屋。如果第 i 个地块放房屋，则第 i-1 个地块不能放；如果第 i 个地块不放房屋，则第 i-1 个地块可放可不放。

  2. 状态转移方程：设 f[i] 表示单侧 i 个地块的方案数。我们可以用两个变量表示状态：

    • house: 第 i 个位置放房屋的方案数
    • empty: 第 i 个位置不放房屋的方案数

    状态转移为：

    • 新的 house = 之前的 empty（只有前一个位置为空，当前位置才能放房屋）
    • 新的 empty = 之前的 house + 之前的 empty（前一个位置无论什么状态，当前都能为空）

  3. 斐波那契规律：实际上单侧的方案数遵循斐波那契数列：f(1)=2, f(2)=3, f(n)=f(n-1)+f(n-2)。

  4. 两侧组合：由于两侧街道是独立的，总方案数 = 单侧方案数的平方。

推荐解法：使用动态规划计算单侧方案数，然后平方得到最终答案。

代码实现

class Solution {
public:
    int countHousePlacements(int n) {
        const int MOD = 1e9 + 7;
        
        // 计算单侧街道的方案数
        long long house = 1; // 当前位置放房屋的方案数
        long long empty = 1; // 当前位置不放房屋的方案数
        
        for (int i = 2; i <= n; i++) {
            long long newHouse = empty;
            long long newEmpty = (house + empty) % MOD;
            house = newHouse;
            empty = newEmpty;
        }
        
        long long oneSide = (house + empty) % MOD;
        return (oneSide * oneSide) % MOD;
    }
};

class Solution:
    def countHousePlacements(self, n: int) -> int:
        MOD = 10**9 + 7
        
        # 计算单侧街道的方案数
        house, empty = 1, 1  # 当前位置放房屋和不放房屋的方案数
        
        for i in range(2, n + 1):
            new_house = empty
            new_empty = (house + empty) % MOD
            house, empty = new_house, new_empty
        
        one_side = (house + empty) % MOD
        return (one_side * one_side) % MOD

public class Solution {
    public int CountHousePlacements(int n) {
        const int MOD = 1000000007;
        
        // 计算单侧街道的方案数
        long house = 1; // 当前位置放房屋的方案数
        long empty = 1; // 当前位置不放房屋的方案数
        
        for (int i = 2; i <= n; i++) {
            long newHouse = empty;
            long newEmpty = (house + empty) % MOD;
            house = newHouse;
            empty = newEmpty;
        }
        
        long oneSide = (house + empty) % MOD;
        return (int)((oneSide * oneSide) % MOD);
    }
}

/**
 * @param {number} n
 * @return {number}
 */
var countHousePlacements = function(n) {
    const MOD = 1e9 + 7;
    
    // 计算单侧街道的方案数
    let house = 1; // 当前位置放房屋的方案数
    let empty = 1; // 当前位置不放房屋的方案数
    
    for (let i = 2; i <= n; i++) {
        let newHouse = empty;
        let newEmpty = (house + empty) % MOD;
        house = newHouse;
        empty = newEmpty;
    }
    
    let oneSide = (house + empty) % MOD;
    return (oneSide * oneSide) % MOD;
};
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

复杂度类型大小
时间复杂度O(n)
空间复杂度O(1)

相关题目