2320. Count Number of Ways to Place Houses

Question

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. 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 10<sup>9</sup><span> </span>+ 7.

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

Solution

计算单侧河道可以放置的种类。
一开始用的是DFS搜素来计算可以放置的种类。
计算后发现是以（2，3）开始的斐波那契数列。

因此直接计算n位置的斐波那契数列值即可。
然后两边可以匹配的种类就是其平方。

记忆化搜索

在计算斐波那契数列时，由于要多次重复计算前面的位置，因此可以采用记忆化搜索记录对应的斐波那契额值。

Code

class Solution {
    long[] memo;
    public int countHousePlacements(int n) {
        memo = new long[n+1];
        long res = fibo(n);
        res *= res;
        res %= 1000000007;
        return (int) res;
    }
    
    private long fibo(int n){
        if(n == 1) return 2;
        else if(n == 2) return 3;
        if(memo[n] != 0) return memo[n];
        memo[n] = fibo(n-1) % 1000000007 + fibo(n-2) % 1000000007;

        return memo[n];
    }
}