题目浅析

  • 想查看原题可以点击题目链接。

  • 简单地说，就是给一个街道的长度 n，现在街道两边都能放置房子，每个占据单位长度 1，在房子不能相邻的情况下，请给出所有建造房子的方案数目。

思路分享

  • 先划分子问题，对于长度 n 的街道放房子，可以先只考虑一边的，因为两边互补干扰，方案数量一致。而如果在第 n 个地方放了房子，这个选择的方案数就相当于在街道前 n-2 的地方放置房子的方案数；如果 n 处不放，n - 1 就可以放，相当于街道前 n-1 的方案数。

  • 然后试着思考下边界条件：当没有地方放房子，只有不放这一种方案；当有一个地方放房子，就有放或不放两种选项。

  • 最后就可以写出记忆化搜索了，再翻译成递推如下。

代码解答（强烈建议自行解答后再看）

  • 参考题解
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
class Solution:
    def countHousePlacements(self, n: int) -> int:
        MOD = 1_000_000_007
        # 尝试记忆化搜索
        @cache
        def dfs(places:int) -> int:
            if places == 1:
                return 2
            elif places == 0:
                return 1
            return (dfs(places-2) + dfs(places-1))  % MOD
        
        one_side = dfs(n)
        return (one_side ** 2) % MOD
        
        # 0 是没有位置的情况，只能不放；1 是可以放或不放
        # f = [1, 2]
        # MOD = 1_000_000_007
        # for i in range(1, n):
        #     f.append((f[-1]+f[-2]) % MOD)
        # return (f[n] ** 2) %MOD