count-number-of-ways-to-place-houses

java

python

python3

mysql

mssql

oraclesql

csharp

javascript

typescript

bash

swift

kotlin

dart

golang

ruby

scala

rust

racket

erlang

elixir

pythondata

postgresql

cangjie

Algorithms

There is a street with <code>n * 2</code> plots, where there are <code>n</code> plots on each side of the street. The plots on each side are numbered from <code>1</code> to <code>n</code>. 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 <code>109 + 7</code>.

Note that if a house is placed on the <code>ith</code> plot on one side of the street, a house can also be placed on the <code>ith</code> plot on the other side of the street.

&nbsp;
Example 1:

<pre>
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.
</pre>

Example 2:
<img alt="" src="https://assets.leetcode.com/uploads/2022/05/12/arrangements.png" style="width: 500px; height: 500px;" />
<pre>
Input: n = 2
Output: 9
Explanation: The 9 possible arrangements are shown in the diagram above.
</pre>

&nbsp;
Constraints:

<ul>
	<li><code>1 &lt;= n &lt;= 104</code></li>
</ul>

countHousePlacements

Count Number of Ways to Place Houses

Climbing Stairs

climbing-stairs

爬楼梯

House Robber

house-robber

打家劫舍

Dynamic Programming

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

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

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

&nbsp;

示例 1：

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

示例 2：
<img alt="" src="https://assets.leetcode.com/uploads/2022/05/12/arrangements.png" style="width: 500px; height: 500px;">
<pre>输入：n = 2
输出：9
解释：如上图所示，共有 9 种可能的放置方式。
</pre>

&nbsp;

提示：

<ul>
	<li><code>1 &lt;= n &lt;= 104</code></li>
</ul>