Polynomial time solution for Constrained Version of Tetris Problem

Question

Tetris is known to be NP-complete problem in general.  However, in this constrained version, we only consider the straight tetrominoes, and further, we cannot rotate them.

We can make the general assumptions that the board is w x h (width x height).  We can see the entire sequence of tetrominoes, which is n units long and only consists of straight tetrominoes (horizontal or vertical).  We can place those tetrominoes wherever we like, but we cannot rotate them.

We receive k points for each row that becomes full.  The full row is then cleared away.

​We need to maximize the score before the height reaches h (not including the cleared rows).

Answer 1

The easiest way I think of is the exhaustive method. Do it with a matrix. It should be polynomial time. I cannot find a method to quickly make sure it is optimal without exhaustive method because the result seems to change time by time. I am not sure but constrained version seems do not change the time complicity? It only adds 4 possibilities.