-1

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.

Taryn East
  • 27,486
  • 9
  • 86
  • 108
delo
  • 11
  • 1
  • That formatting better? Also, you're not going to get a lot of play by asking someone to do your CS homework as your first SO action. – Jed Smith Nov 12 '09 at 02:15

2 Answers2

0

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!!

AntonioMO
  • 898
  • 1
  • 6
  • 16
0

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.

eulerfx
  • 36,769
  • 7
  • 61
  • 83