気になることがあります。この情報を指示として持つ建物の橋の問題を解決しようとしています。
橋
を架ける 水平方向の川が中心を通過する 2 次元マップを考えてみましょう。南岸には x 座標 a(1) ... a(n) の n 個の都市があり、北岸には x 座標 b(1) ... b(n) の n 個の都市があります。
2 つの橋が交差しないように、できるだけ多くの都市の南北のペアを橋で接続する必要があります。都市を接続する場合、北岸の都市 i と南岸の都市 i のみを接続できます。」
私はスタック オーバーフローについて調査し、次のような非常に役立つトピックを見つけました
。
動的計画法を使用して最長増加サブシーケンスを
決定する方法は?
しかし、私が LIS を思いついたとき、1 つのサンプル リストを手で解決しようとしました。私が持っているとしましょう
Northern Bank >> 7 4 3 6 2 1 5
Southern Bank >> 5 3 2 4 6 1 7
ソート後サザンバンク
Northern Bank >> 1 3 4 6 7 2 5
Southern Bank >> 1 2 3 4 5 6 7
LIS の長さは "5" であると想定されていますが、実際には最初のリストでは、(3,2,1) を作成できるブリッジは 3 つだけです。それで、私はLISを誤解しましたか、それとも橋の問題を構築するのにうまくいかない例外はありますか?