790. Domino and Tromino Tiling

Link

Solution

1. Draw the combination of N = 1~5, and try to conduct the formula

dp[n] = 2*dp[n-1] + dp[n-3]

   public int numTilings(int N) {
        
        if(N < 2)
            return 1;
        long[] dp = new long[1001];
        dp[0] = 1; // only one way to tile nothing
        dp[1] = 1; 
        dp[2] = 2;
        dp[3] = 5;
        //dp[i] = dp[i-1] + dp[i-2] + 2*(dp[i-3] + dp[i-4] + .... dp[0]);
        //      = dp[i-1] + dp[i-2] + 2*dp[i-3] + 2*(dp[i-4]+ dp[i-5] + ... dp[0])
        //      = dp[i-1] + dp[i-1] + dp[i-3]
        //      = 2*dp[i-1] + dp[i-3]
        
        for(int i = 3; i <= N; i++){
            dp[i]= (2*dp[i-1] + dp[i-3])%((long)(1e9 + 7));
        }
        return (int)dp[N];
        
    }