# Find recurrence in DP

## 790. Domino and Tromino Tiling

`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;            }};`

--

--

## More from Jimmy Shen

Data Scientist/MLE/SWE @takemobi

Love podcasts or audiobooks? Learn on the go with our new app.