Find recurrence in DP

Leetcode 790. Domino and Tromino Tiling

790. Domino and Tromino Tiling

Image source [1]

Code with comments

const int mod = 1e9 + 7;
class Solution {
public:
    int numTilings(int N) {
        // dp[0] = {}
        // dp[1] = {|}
        // dp[2] = {||}, {==}
        // dp[3]= dp[2] + {|},  dp[1]+ {==}, dp[0]+
        // **#  *##
        // *##  **#
        // dp[4] = dp[3] + {|}, dp[2] + {==}, dp[1] + 
        // **#  *##
        // *##  **#
        // + dp[0] +
        // **##   *^^#
        // *^^#   **##
        // dp[n] = dp[n-1]*1 + dp[n-2]*1 + dp[n-3]*2+ dp[n-4]*2 ... dp[0]*2
        // dp[n-1] = dp[n-2] + dp[n-3] + dp[n-4]*2 ....dp[0]*2
        // dp[n]-dp[n-1] = dp[n-1] + dp[n-3]
        // dp[n] = 2*dp[n-1] + dp[n-3]
        // n-3:a, n-2:b, n-1:c
        // ret = 2*c + a
        if (N == 1) return 1;
        if (N == 2) return 2;
        if (N == 3) return 5;
        // 0, 1, 2
        int a = 1, b = 1, c = 2 , new_c = 0;
        for (int i = 3; i <= N; ++i)
        {
            new_c = (2*c >= mod? 2*c % mod : 2*c) + a;
            a = b;
            b = c;
            c = new_c;
            if (c >= mod) c %= mod;
        }
        return c;
        
    }
};

Reference

[1] https://leetcode.com/problems/domino-and-tromino-tiling/discuss/116581/Detail-and-explanation-of-O(n)-solution-why-dpn2*dn-1+dpn-3