2320. Count Number of Ways to Place Houses

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 109 + 7.

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

class Solution {
    int dp[10101][4], mod = 1e9 + 7;
    int helper(int n, int mask) {
        if(n == 0) return 1;
        if(dp[n][mask] != -1) return dp[n][mask];
        int& res = dp[n][mask] = helper(n - 1, 0);
        for(int i = 1; i <= 3; i++) {
            if(mask & i) continue;
            res = (res + helper(n-1,i)) % mod;
        }
        return res;
    }
public:
    int countHousePlacements(int n) {
        memset(dp, -1, sizeof dp);
        return helper(n, 0);
    }
};