Find recurrence in DP

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;

}
};

--

--

Get the Medium app

A button that says 'Download on the App Store', and if clicked it will lead you to the iOS App store
A button that says 'Get it on, Google Play', and if clicked it will lead you to the Google Play store