Domino and Tromino tiling problem | 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
MOD = 1e9 + 7 NEW_LINE def numTilings ( N ) : NEW_LINE INDENT if ( N < 3 ) : NEW_LINE INDENT return N NEW_LINE DEDENT dp = [ [ 0 ] * 3 for i in range ( N + 1 ) ] NEW_LINE dp [ 0 ] [ 0 ] = dp [ 1 ] [ 0 ] = 1 NEW_LINE dp [ 1 ] [ 1 ] = dp [ 1 ] [ 2 ] = 1 NEW_LINE for i in range ( 2 , N + 1 ) : NEW_LINE INDENT dp [ i ] [ 0 ] = ( dp [ i - 1 ] [ 0 ] + dp [ i - 2 ] [ 0 ] + dp [ i - 2 ] [ 1 ] + dp [ i - 2 ] [ 2 ] ) % MOD NEW_LINE dp [ i ] [ 1 ] = ( dp [ i - 1 ] [ 0 ] + dp [ i - 1 ] [ 2 ] ) % MOD NEW_LINE dp [ i ] [ 2 ] = ( dp [ i - 1 ] [ 0 ] + dp [ i - 1 ] [ 1 ] ) % MOD NEW_LINE DEDENT return int ( dp [ N ] [ 0 ] ) NEW_LINE DEDENT N = 3 NEW_LINE print ( numTilings ( N ) ) NEW_LINE