dynamic programming: finding largest non-overlapping squares

Question

I really have no idea how to do this using dynamic programming: Problem: I need to find the 2 largest non overlapping squares of a table For example:

5 6
R F F R R F
F F F F F F
R R F F F F
F F F F F F
F F F F F F

The numbers 5 and 6 are the number of rows and columns respectively, and “R” means reserved and “F” means free. In this case the largest square is

F F F F
F F F F
F F F F
F F F F

and the second largest (non-overlapping with the previous one) is

F F
F F

So far I have put the values into a 2D array, but do not know what to do after. Tried to reference 0-1 knapsack and LCS, but really I have no clue on what values I should put into my table.

Answer 1

Well, your first task when designing a dynamic programming algorithm should be to find a recursive solution to the problem. After that is done, converting it to a dynamic programming algorithm is almost trivial ;).

Some tips that could/could not help:

A possible base case is obvious: any two 1 cell squares are always non-overlapping.

Bear in mind that the largest of the two squares can not cover the entire table (because then you wont have a second largest), so it cannot be of rows:columns size.

You should have an "score" to each solution you evaluate, to see what's the best one.This score is obviously size1 + size2, with the condition that size1 should be the maximum possible.

Good luck!!

Answer 2

This is a variation of the Longest Common Substring Problem not LCS (Longest common subsequence). Picture two strings you are comparing as being sides of a rectangle with their characters as the squares. An "F" in a square would mean a match between two characters in the strings, and thus the largest square is the longest common substring.