leetcode 2320. Count Number of Ways to Place Houses（python）
原题形容
There is a street with n * 2 plots, where there are n plots on each side of the street. The plots on each side are numbered from 1 to n. On each plot, a house can be placed. Return the number of ways houses can be placed such that no two houses are adjacent to each other on the same side of the street. Since the answer may be very large, return it modulo 10^9 + 7.
Note that if a house is placed on the ith plot on one side of the street, a house can also be placed on the ith plot on the other side of the street.
Example 1:
Input: n = 1
Output: 4
Explanation:
Possible arrangements:
1. All plots are empty.
2. A house is placed on one side of the street.
3. A house is placed on the other side of the street.
4. Two houses are placed, one on each side of the street.Example 2:
Input: n = 2
Output: 9
Explanation: The 9 possible arrangements are shown in the diagram above.Note:
1 <= n <= 10^4
暴力 DFS
依据题意，有一条街道有 n * 2 个地块，街道的每一侧都有 n 个地块。每边的地块从 1 到 n 编号。在每个地块上，能够搁置一所房子。返回能够搁置屋宇的形式数，以使街道的同一侧没有两个屋宇彼此相邻。因为答案可能十分大，因而以 10^9 + 7 为模返回。如果房子放在街道一侧的第 i 个地块上，那么房子也能够放在街道另一侧的第 i 个地块上。
其实通过找法则咱们能够发现，：
n = 1 时候，一侧搁置屋宇形式数为 2，两侧总共能够搁置屋宇形式数为 4
n = 2 时候，一侧搁置屋宇形式数为 3，两侧总共能够搁置屋宇形式数为 9
n = 3 时候，一侧搁置屋宇形式数为 5，两侧总共能够搁置屋宇形式数为 25
n = 4 时候，一侧搁置屋宇形式数为 8，两侧总共能够搁置屋宇形式数为 64
…
能够发现随着 n 的减少，一侧搁置屋宇形式数是斐波那契数列，咱们只有晓得 n 时一侧搁置屋宇形式数，而后计算平方再取 10^9 + 7 的模即可。
所以咱们的要害是解决斐波那契数列的计算，这里咱们先应用最无脑的暴力 DFS 进行解题递归法则就是 :dfs(n) = dfs(n-1)+dfs(n-2)
依据然而我预测会超时（其实我就是运行报错了），因为下面限度条件中写了 n 最大是 10000，咱们在进行递归的时候是自顶向下，会有很多反复的计算，如计算 dfs(10) 就要先进行 dfs(9) 和 dfs(8) 的计算，然而在计算 dfs(9) 的时候又计算了一次 dfs(8)，以此类推，所以在 n 为 10000 的时候必定会超时，dfs 计算过程就像是一棵二叉树自顶向下决裂。
工夫复杂度为 O(2^N)，空间复杂度为 O(N)。
解答
class Solution(object):
def countHousePlacements(self, n):
"""
:type n: int
:rtype: int
"""
if n == 1: return 4
if n == 2: return 9
def dfs(n):
if n == 1: return 2
if n == 2: return 3
return dfs(n - 2) + dfs(n - 1)
return pow(dfs(n), 2) % (10 ** 9 + 7)
运行后果
Time Limit Exceeded
记忆化 DFS
果然不出所料超时了，其实咱们曾经剖析了起因了，无非就是有反复的计算，所以咱们只有退出了记忆化，这样应用了记忆化的 DFS，在计算 dfs(10) 就要先进行 dfs(9) 和 dfs(8) 的计算，然而在计算 dfs(9) 的时候咱们须要的 dfs(8) 曾经计算并保留下来了，所以咱们只须要间接应用后果即可，这样相当于把一棵自顶向下的二叉树进行了剪枝操作，将反复计算的过程都去掉了，咱们的整个计算过程都只是计算了 dfs(n)、dfs(n-1)、…、dfs(1) 一遍，没有多余的操作。
所以工夫复杂度为 O(N)，空间复杂度为 O (N)。
解答
class Solution(object):
def countHousePlacements(self, n):
"""
:type n: int
:rtype: int
"""
if n == 1: return 4
if n == 2: return 9
d = {1:2, 2:3}
def dfs(n):
if n == 1: return 2
if n == 2: return 3
if n in d:
return d[n]
d[n] = dfs(n - 2) + dfs(n - 1)
return d[n]
return pow(dfs(n), 2) % (10 ** 9 + 7)
运行后果
150 / 150 test cases passed.
Status: Accepted
Runtime: 757 ms
Memory Usage: 61.6 MB动静布局
其实仔细的同学曾经发现了下面的解法只管应用了 DFS，然而其实曾经有了状态转移方程 :
dfs(n) = dfs(n – 2) + dfs(n – 1)
所以咱们能够应用动静布局来解题，动静布局和 DFS 不同之处在于，DFS 是自顶向下进行计算而后又把后果逐层往上返回到顶，而动静布局的计算时自底向上的，从 dp[1]、dp[2] 开始，利用状态转移方程间接一次性计算到 dp[n]。
工夫复杂度为 O(N)，空间复杂度为 O(N)。这里尽管工夫复杂度和空间复杂度和下面一样，然而耗时会更少，耗费内存也更少，因为少了递归栈的解决和记忆化字典的解决两个操作。
解答
class Solution(object):
def countHousePlacements(self, n):
"""
:type n: int
:rtype: int
"""
if n == 1: return 4
if n == 2: return 9
dp = [0] * (n+1)
dp[1] = 2
dp[2] = 3
for i in range(3, n+1):
dp[i] = dp[i-2] + dp[i-1]
return pow(dp[n], 2) % (10 ** 9 + 7)
运行后果
150 / 150 test cases passed.
Status: Accepted
Runtime: 192 ms
Memory Usage: 18.2 MB状态压缩的动静布局
应用动静布局也有两种模式，一种应用列表 dp，自底向上进行动静布局的惯例计算失去最初的后果 dp[n]，就像下面介绍的一样，另一种咱们发现斐波那契数列中，其实以后值只与前前个与前个两个数字无关，所以我这里为了节俭空间，应用了压缩状态的动静布局，只须要三个变量即可实现状态的转移。
工夫复杂度为 O(N)，空间复杂度为 O(1)。
解答
class Solution(object):
def countHousePlacements(self, n):
"""
:type n: int
:rtype: int
"""
if n == 1: return 4
if n == 2: return 9
pre, cur = 2, 3
for i in range(3, n+1):
tmp = pre + cur
pre = cur
cur = tmp
return (cur * cur) % (10**9+7)运行后果
150 / 150 test cases passed.
Status: Accepted
Runtime: 154 ms
Memory Usage: 14 MB