Dynamic programming rectangular grid You are given a 40x40 grid. Each point of the grid is either 0 or 1. You are also given an infinite amount of 1x40 rectangular slabs.

How to find out the minimum number of slabs required to cover all the points which have a value 1?

NOTE: The 1x40 slabs can overlap with each other.
I'm assuming you're only allowed to use the 1x40 slabs horizontally or vertically. They thus cover entire rows or columns. We can rephrase your problem as minimum vertex cover in a bipartite graph. The bipartite graph consists of 40 row vertices and 40 column vertices. Connect two vertices if the corresponding point in the grid is 1. The minimum number of slabs needed to cover all 1s is exactly the minimum vertex cover in this bipartite graph. In bipartite graphs, minimum vertex cover equals maximum matching, so the problem is algorithmically feasible. In order to find a concrete algorithm, just look for algorithms for solving minimum vertex cover on bipartite graphs.