Leetcode Problem 2320. Count Number of Ways to Place Houses

2320. Count Number of Ways to Place Houses

Leetcode Solutions

Dynamic Programming Approach with Fibonacci Sequence

  1. Initialize two variables, prev and curr, to represent the number of ways to place houses on one side of the street for the previous and current positions, respectively.
  2. Set prev to 1 and curr to 2, which corresponds to the base cases of the Fibonacci sequence.
  3. Iterate from 2 to n, updating prev and curr at each step to reflect the Fibonacci sequence.
  4. At each iteration, calculate the new curr as the sum of prev and the old curr, then update prev to the old curr.
  5. After the loop, the value of curr represents the number of ways to place houses on one side of the street for n plots.
  6. Return the square of curr modulo 10^9 + 7 to get the total number of ways for both sides of the street.
UML Thumbnail

Recursive Approach with Memoization

Ask Question

Programming Language
image/screenshot of info(optional)
Full Screen
Loading...

Suggested Answer

Answer
Full Screen
Copy Answer Code
Loading...