Matrices Generated Using Rectangles
Python 2, 333 bytes



lambda g,l=len:min(i for i in r(l(g)*l(g[0])+1)if g in o(l(g[0]),l(g),[[0]*l(g[0])for _ in" "*l(g)],set(sum(g,[])),i))
o=lambda w,h,g,s,I:I and sum([o(w,h,n,s,I-1)for n in[[[x&lt;=j&lt;=X&lt;[]&gt;Y&gt;=i&gt;=y and S or E for j,E in e(R)]for i,R in e(g)]for x in r(w)for X in r(x,w)for y in r(h)for Y in r(y,h)for S in s]],[])or[g]
r=range
e=enumerate


Try it online!

This only works in theory, because in practice, it takes way too long if you have more than about 5 elements in the grid.

Since this is code-golf, I apologize for the inefficiency, but efficiency would require more thought and FAR more bytes.

This code does the same thing at the cost of 5 bytes, but short-circuits, meaning that a larger grid with a small answer may finish somewhat earlier... the difference in viable search space is negligible, but just in case you wanted to test it a bit more.

The reason this is so slow is because it looks from \$0\$ up to \$W\times H\$, generating every possible \$W\times H\$ grid that can be achieved with the elements of the grid with that many steps being used.