Readme

2320.Count-Number-of-Ways-to-Place-Houses

本题的本质就是House Robber。House Robber求的是“无相邻元素的序列”的最大元素和。本题求的是“无相邻元素的序列”的方案总数。

解法1：DP

令dp[i][0]表示第i个位置不放置建筑的方案总数，dp[i][1]表示第i个位置放置建筑的方案总数。不难有转移方程

dp[i][0] = (dp[i-1][0] + dp[i-1][1])%M;
dp[i][1] = dp[i-1][0];

边界条件是dp[0][0]和dp[0][1]。考虑我们的位置是从1开始的，那么dp[0][]意味着根本没有位置放置建筑，故有

dp[0][0] = 1
dp[0][1] = 0

最终的答案是考察第n处位置，放置建筑与不放置建筑的方案总和，即dp[n][0]+dp[n][1].

解法2：Fibonacci

解答区的很多帖子都提到了斐波那契数列。如果令dp[i]表示前i个plot里合法的方案，那么dp[i]呈现的是斐波那契数列的性质。

例如dp[1] = 2, dp[2] = 3, dp[3] = 5, ....

但是dp[i]=dp[i-2]+dp[i-1]的实际意义，确实非常难以解释的。参见我对LC美服评论区的质疑

解法3：组合数

假设我们拆出一个小问题来看，在n个位置里放置k个元素，要求没有元素相邻，有多少种方案？这个答案是C(n-(k-1), k).

解释如下。我们将n个位置里拿走k-1个位置。剩下的位置里任意放置k个元素。然后再将拿走的k-1个位置插在已经放置的k个元素中间，就完美地实现了题目要求，即没有任何两个元素相邻。

我们遍历k，从最小的0，最大直至2*k-1<=n(否则必然会有两个元素相邻），将所有的组合数都加起来，就是答案。

当然，将这些组合数单独逐个求出，效率是低的，这个代码会TLE。