Domino and Tromino tiling problem | C ++ program for the above approach ; Function to find the total number of ways to tile a 2 * N board using the given types of tile ; If N is less than 3 ; Store all dp - states ; Base Case ; Traverse the range [ 2 , N ] ; Update the value of dp [ i ] [ 0 ] ; Update the value of dp [ i ] [ 1 ] ; Update the value of dp [ i ] [ 2 ] ; Return the number of ways as the value of dp [ N ] [ 0 ] ; Driver Code
#include <bits/stdc++.h> NEW_LINE using namespace std ; const long long MOD = 1e9 + 7 ; int numTilings ( int N ) { if ( N < 3 ) { return N ; } vector < vector < long long > > dp ( N + 1 , vector < long long > ( 3 , 0 ) ) ; dp [ 0 ] [ 0 ] = dp [ 1 ] [ 0 ] = 1 ; dp [ 1 ] [ 1 ] = dp [ 1 ] [ 2 ] = 1 ; for ( int i = 2 ; i <= N ; i ++ ) { dp [ i ] [ 0 ] = ( dp [ i - 1 ] [ 0 ] + dp [ i - 2 ] [ 0 ] + dp [ i - 2 ] [ 1 ] + dp [ i - 2 ] [ 2 ] ) % MOD ; dp [ i ] [ 1 ] = ( dp [ i - 1 ] [ 0 ] + dp [ i - 1 ] [ 2 ] ) % MOD ; dp [ i ] [ 2 ] = ( dp [ i - 1 ] [ 0 ] + dp [ i - 1 ] [ 1 ] ) % MOD ; } return dp [ N ] [ 0 ] ; } int main ( ) { int N = 3 ; cout << numTilings ( N ) ; return 0 ; }