динамическое программирование: поиск самых больших непересекающихся квадратов

Question

Я действительно понятия не имею, как это сделать с помощью динамического программирования: Проблема: Мне нужно найти 2 самых больших не перекрывающихся квадрата таблицы Например:

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

Числа 5 и 6 - это количество строк и столбцов соответственно, а «R» означает зарезервированное и «F» означает свободный. В этом случае самый большой квадрат -

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

, а второй по величине (не совпадает с предыдущим) -

F F
F F

Пока что я поместил значения в двумерный массив, но не знаю, что делать после. Пытался сослаться на рюкзак 0-1 и LCS, но на самом деле я понятия не имею, какие значения я должен поместить в свою таблицу.

Answer 1

Это вариант самой длинной общей проблемы с подстрокой не LCS (самая большая общая подпоследовательность). Представьте две строки, которые вы сравниваете как стороны прямоугольника, а их символы - квадраты. «F» в квадрате будет означать совпадение между двумя символами в строках, и поэтому самый большой квадрат - это самая длинная общая подстрока.

Answer 2

Ну, ваша первая задача при разработке алгоритма динамического программирования должна состоять в том, чтобы найти рекурсивное решение проблемы. После того, как это сделано, преобразование его в алгоритм динамического программирования почти тривиально;).

Несколько советов, которые могли / не могли помочь:

Возможный базовый случай очевиден: любые два квадрата 1 ячейки всегда не перекрываются.

Имейте в виду, что самый большой из двух квадратов не может охватывать всю таблицу (потому что тогда у вас не будет второго по величине), поэтому он не может быть строк: размер столбцов.

Вы должны иметь «оценку» для каждого решения, которое вы оцениваете, чтобы увидеть, какое решение является лучшим. Это, очевидно, size1 + size2 с условием, что size1 должен быть максимально возможным.

Удачи !!