Count ways to tile an N | Function to count the ways to tile N * 1 board using 1 * 1 and 2 * 1 tiles ; dp [ i ] : Stores count of ways to tile i * 1 board using given tiles ; Base Case ; Iterate over the range [ 2 , N ] ; Fill dp [ i ] using the recurrence relation ; Driver Code ; Given N ; Function Call
def countWaysToTileBoard ( N ) : NEW_LINE INDENT dp = [ 0 ] * ( N + 1 ) NEW_LINE dp [ 0 ] = 1 NEW_LINE dp [ 1 ] = 2 NEW_LINE for i in range ( 2 , N + 1 ) : NEW_LINE INDENT dp [ i ] = ( 2 * dp [ i - 1 ] + dp [ i - 2 ] ) NEW_LINE DEDENT print ( dp [ N ] ) NEW_LINE DEDENT if __name__ == " _ _ main _ _ " : NEW_LINE INDENT N = 2 NEW_LINE countWaysToTileBoard ( N ) NEW_LINE DEDENT