10. In the process of designing an $n$ storey building, an architect designed $k$ types of floor modules. Even though the ground floor can use any of the $k$ modules, subsequent floors need to satisfy compatibility constraints. For each module $M_{i}$, there is some subset $B_{i}$ of modules on top of which $M_{i}$ can bebuilt. As an example consider the case when $k = 3$ and say $B_{1}=\left \{ M_{1},M_{2},M_{3} \right \},$ $B_{2}=\left \{ M_{1},M_{3} \right \}$ and $B_{3}=\left \{ M_{1},M_{2} \right \}$. Then a $4$-story building can have the floor plan (from ground to $4$) as $M_{2}M_{1}M_{2}M_{3}$ but not $M_{3}M_{2}M_{2}M_{3}$. The additional cost of adding an extra floor with say a floor module $M_{j}$ can change depending on the structure of the building so far. What is the tightest upper bound on the run-time of
an algorithm to compute the cheapest floor plan for the $n$ storey building.
A. $O(k^{n})$
B. $O(n^{k})$
C. $O(nk)$
D. $O(nk^{2})$
E $O(n^{2}k)$
