统计放置房子的方式数
难度:
标签:
题目描述
一条街道上共有 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
/*
* 思路：
* 使用Java Stream API实现动态规划。我们首先初始化dp数组，
* 然后用IntStream进行操作，生成dp数组，最后计算结果并取模。
*/
import java.util.stream.IntStream;
public class Solution {
public int countHousePlacements(int n) {
int MOD = 1000000007;
if (n == 1) return 4;
long[] dp = new long[n + 1];
dp[0] = 1;
dp[1] = 2;
IntStream.range(2, n + 1).forEach(i -> dp[i] = (dp[i - 1] + dp[i - 2]) % MOD);
long result = (dp[n] * dp[n]) % MOD;
return (int) result;
}
}解释
方法:
这个问题可以通过动态规划来解决。考虑一条街道的一侧，我们需要计算不相邻放置房子的方式数。定义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)
代码细节讲解
🦆
在解题的动态规划方法中，为什么可以将问题简化为计算单边街道的放置方式数然后平方得到结果？
▷🦆
状态转移方程`f[i] = f[i-1] + f[i-2]`中，为什么加入f[i-2]是合理的？在放置房子的情况下，为什么不需要考虑更远的地块之间的关系？
▷🦆
为什么初始化条件是`f[0]=1`和`f[1]=2`？这两个初始值在逻辑上是如何对应到放置房子的情况的？
▷🦆
在计算函数`countHousePlacements`时，为什么直接返回`f[n] ** 2 % MOD`，其中的平方操作是如何保证不会遗漏任何放置组合的可能性的？
▷