動的計画法を使用してこれを行う方法が本当にわかりません。問題：テーブルの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
2番目に大きい（前のものと重複しない）は
F F
F F
これまでのところ、値を2D配列に入れましたが、後で何をすべきかわかりません。0-1ナップザックとLCSを参照しようとしましたが、実際には、テーブルにどの値を入れるべきかわかりません。
動的計画法のアルゴリズムを設計するときの最初のタスクは、問題の再帰的な解決策を見つけることです。それが完了したら、それを動的計画法アルゴリズムに変換するのはほとんど簡単です;)。
役立つ/役に立たないヒント:
考えられる基本的なケースは明らかです。2 つの 1 セルの正方形は常に重なりません。
2 つの正方形のうち最大のものはテーブル全体をカバーできないことに注意してください (2 番目に大きいものは存在しないため)。したがって、行:列のサイズにすることはできません。
評価する各ソリューションに「スコア」を付けて、最適なものを確認する必要があります。このスコアは明らかにサイズ 1 + サイズ 2 であり、サイズ 1 が可能な最大値である必要があります。
幸運を！！
これは、LCS (Longest common subsequence) ではなく、 Longest Common Substring Problemのバリエーションです。比較している 2 つの文字列が四角形の辺であり、その文字が四角形であると想像してください。正方形の「F」は、文字列内の 2 つの文字が一致することを意味するため、最大の正方形が最長の共通部分文字列になります。