Count Number of Ways to Place Houses LeetCode solution in Python

1
class Solution:
2
    def countHousePlacements(self, n: int) -> int:
3

4
        @lru_cache(None)
5
        def rec(i, k):
6

7
            # i is the index of the house
8
            # k is the state of last house, 1 if there was a house on the last index else 0
9

10
            if i >= n:
11
                return 1
12

13
            elif k == 0:
14
                return rec(i + 1, 1) + rec(i + 1, 0)
15

16
            else:
17
                return rec(i + 1, 0)
18

19
        # l1 are the combinations possible in lane 1, the final answer will be the square
20
        # of of l1 as for every combination of l1 there will be "l1" combinations in lane2.
21

22
        l1 = rec(1, 0) + rec(1, 1)
23

24
        mod = 10**9 + 7
25
        return pow(l1, 2, mod)  # use this when there is mod involved along with power