790. Domino and Tromino Tiling

You have two types of tiles: a 2 x 1 domino shape and a tromino shape. You may rotate these shapes.

Given an integer n, return the number of ways to tile an 2 x n board. Since the answer may be very large, return it modulo 109 + 7.

In a tiling, every square must be covered by a tile. Two tilings are different if and only if there are two 4-directionally adjacent cells on the board such that exactly one of the tilings has both squares occupied by a tile.

class Solution {
    int dp[1001];
    int mod = 1e9 + 7;
    int helper(int n) {
        if(n < 0) return 0;
        if(n <= 1) return 1;
        if(n == 2) return 2;
        if(n == 3) return 5;
        if(dp[n] != -1) return dp[n];
        dp[n] = 0;
        dp[n] = (dp[n] + 2 * helper(n - 1)) % mod;
        dp[n] = (dp[n] + helper(n - 3)) % mod;
        return dp[n];
    }
public:
    int numTilings(int n) {
        memset(dp, -1, sizeof dp);
        return helper(n);
    }
};