Count Number of Ways to Place Houses — LeetCode 2320 Python Solution

The problem

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.

Example

Input

n = 1

Output

4

Explanation

Possible arrangements:

Python solution

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

Complexity

Pattern: Dynamic Programming

Define a state, write the transition, and stop recomputing the same subproblem. LeetCode 2320. Count Number of Ways to Place Houses is filed here on both counts: the reference solution below belongs to the algorithm family this hub collects, and LeetCode tags it Dynamic Programming.

The dynamic programming guide has the Python template for the pattern and the 481 LeetCode problems that use it.

Related problems