What is the optimal approach to solve Count Number of Ways to Place Houses?

The optimal approach involves dynamic programming, first solving for one side of the street and then extending it to both sides while ensuring no adjacent houses.

How do I handle large numbers in this problem?

You should return the result modulo 10^9 + 7 to handle large numbers and avoid overflow.

What is the time complexity of solving this problem?

The time complexity of the solution is O(n), where n is the number of plots, as the algorithm iterates through the plots once.

Can this problem be solved with a greedy approach?

A greedy approach may fail because it does not consider the possibility of placing houses on both sides of the street in a way that maximizes the solution.

What is state transition dynamic programming?

State transition dynamic programming is a method of solving problems by breaking them down into simpler subproblems and transitioning between states based on decisions made at each step.

#2320

Medium

auto_awesome状态·转移·动态规划

LeetCode 题解工作台

统计放置房子的方式数

一条街道上共有 n * 2 个地块，街道的两侧各有 n 个地块。每一边的地块都按从 1 到 n 编号。每个地块上都可以放置一所房子。现要求街道同一侧不能存在两所房子相邻的情况，请你计算并返回放置房屋的方式数目。由于答案可能很大，需要对 10 9 + 7 取余后再返回。注意，如果一所房子放置在…

动态规划

题目描述

一条街道上共有 n * 2 个地块，街道的两侧各有 n 个地块。每一边的地块都按从 1 到 n 编号。每个地块上都可以放置一所房子。

现要求街道同一侧不能存在两所房子相邻的情况，请你计算并返回放置房屋的方式数目。由于答案可能很大，需要对 10⁹ + 7 取余后再返回。

注意，如果一所房子放置在这条街某一侧上的第 i 个地块，不影响在另一侧的第 i 个地块放置房子。

示例 1：

输入：n = 1
输出：4
解释：
可能的放置方式：
1. 所有地块都不放置房子。
2. 一所房子放在街道的某一侧。
3. 一所房子放在街道的另一侧。
4. 放置两所房子，街道两侧各放置一所。

示例 2：

输入：n = 2
输出：9
解释：如上图所示，共有 9 种可能的放置方式。

提示：

1 <= n <= 10⁴

lightbulb

解题思路

方法一：动态规划

由于街道两侧房子的摆放互不影响，因此，我们可以只考虑一侧的摆放情况，最后将一侧的方案数平方取模得到最终结果。

我们定义 $f[i]$ 表示放置前 $i+1$ 个地块，且最后一个地块放置房子的方案数，定义 $g[i]$ 表示放置前 $i+1$ 个地块，且最后一个地块不放置房子的方案数。初始时 $f[0] = g[0] = 1$ 。

当我们放置第 $i+1$ 个地块时，有两种情况：

如果第 $i+1$ 个地块放置房子，那么第 $i$ 个地块必须不放置房子，因此方案数 $f[i]=g[i-1]$ ；
如果第 $i+1$ 个地块不放置房子，那么第 $i$ 个地块可以放置房子，也可以不放置房子，因此方案数 $g[i]=f[i-1]+g[i-1]$ 。

最终，我们将 $f[n-1]+g[n-1]$ 的平方取模即为答案。

时间复杂度 $O(n)$ ，空间复杂度 $O(n)$ 。其中 $n$ 为街道的长度。

1

2

3

4

5

6

7

8

9

10

11

class Solution:
    def countHousePlacements(self, n: int) -> int:
        mod = 10**9 + 7
        f = [1] * n
        g = [1] * n
        for i in range(1, n):
            f[i] = g[i - 1]
            g[i] = (f[i - 1] + g[i - 1]) % mod
        v = f[-1] + g[-1]
        return v * v % mod

speed

复杂度分析

指标	值
时间	Depends on the final approach
空间	Depends on the final approach

psychology

面试官常问的追问

外企场景

question_mark
The candidate demonstrates an understanding of state transition dynamic programming and can apply it to solve the problem.
question_mark
The candidate breaks down the problem into manageable subproblems, such as solving for one side of the street first.
question_mark
The candidate correctly handles the modulo operation to ensure that the final result fits within the required limits.

warning

常见陷阱

外企场景

error
Overcomplicating the solution by not simplifying the problem to solving for one side of the street first.
error
Neglecting the modulo operation or forgetting to return the result modulo 10^9 + 7.
error
Failing to handle the case where both sides of the street need to be considered independently but with overlapping constraints.

swap_horiz

进阶变体

外企场景

arrow_right_alt
Increase the number of plots n to test the scalability of the DP approach.
arrow_right_alt
Consider constraints such as not allowing houses to be placed on the first or last plot of the street.
arrow_right_alt
Extend the problem to include additional constraints, such as a maximum number of houses that can be placed on the street.

help

常见问题

外企场景

继续练习

#2321 拼接数组的最大分数 #2318 不同骰子序列的数目 #2327 知道秘密的人数