Fitting minimum number of rectangles of width/height 1 into a 2D grid
Ok, so you have a polygon $P$ with integer-length axis-parallel sides and possibly with holes (the shape you want to cover) and you want to partition it into as few $1\times a$ or $b\times 1$ rectangles as possible. At first I thought you wanted the minimum partition into rectangles of arbitrary shapes, which has a known polynomial time solution involving a reduction to maximum independent sets in bipartite graphs. But I think this one is also polynomial, via a different reduction to the same problem.

Draw a graph $G$ that has a vertex for every unit-length line segment that separates two squares of $P$, and that has an edge connecting the vertices for every two perpendicular line segments that share an endpoint. Then the partitions of $P$ into unit-width rectangles correspond one-for-one with independent sets of $G$. If a vertex $v$ of $G$ corresponds to a line segment $s$, then $v$ belongs to a given independent set exactly when the two squares separated by $s$ belong to the same rectangle as each other in the corresponding partition.

Under this correspondence, we have the equation $R=S-I$ where $R$ denotes the number of rectangles in a given partition, $S$ denotes the number of squares in $P$, and $I$ denotes the cardinality of the independent set; this is easy to see by induction on $I$, by removing one independent set element at a time. Since $S$ is fixed, minimizing $R$ is the same as maximizing $I$, and the optimal partition of $P$ corresponds to the maximum independent set of $G$. But $G$ is a bipartite graph (horizontal segments are adjacent only to vertical segments and vice versa) so its maximum independent set may be found in polynomial time (see König's theorem on Wikipedia).