动态规划：找到最大的非重叠正方形 [英] dynamic programming: finding largest non-overlapping squares

问题描述

我真的不知道如何做到这一点使用动态规划：
问题：
我需要找到一个表的2个最大的非重叠正方形
例如：

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

中的数字5和6是行和列的数量分别为和R指保留
与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

和第二大的是

F F
F F

到目前为止，我已经把值转换为二维数组，但不知道以后该怎么办。
试图引用0-1背包和LCS，但实际上我有什么样的价值观，我应该把我的表没有任何线索。

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.

推荐答案

这是最长公共子串问题不LCS（最长公共子）。想象你是比较作为一个长方形的边与他们的字符作为正方形两个字符串。一个F在一个正方形意味着两个字符之间的匹配的字符串，从而最大正方形是最长的共同子串。

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.

这篇关于动态规划：找到最大的非重叠正方形的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！