I was solving one assignment and I am not getting ideas for this, I tried thinking in terms of dp but couldn’t think of optimal substructure. It goes like this :-
I need to find a minimum number of square tiles of dimension less than the dimension of floor given needed to tile that floor, example:-
- for a floor of dimension n=4 we have tiles of size 1, 2, 3. so 4 tiles of 2*2 will do, I suppose that is minimum;
- Another thing is we may have any number of non-optimal solution to this problem, say for n=4 we may have a tile of 3by3 and 7 tiles of 1by1 i.e. total 8 tiles. I also need to count the number of non-optimal unique solutions (ie. same configuration should not be counted twice).
I am attaching a scerenshot for clarity
Any help is appreciated…