最長増加サブシーケンスのアルゴリズムを理解できない

Question

問題がどのように最適なサブ構造を持っているかを理解するために多くのオンラインリソースを使いましたが、すべてを無駄にしましたが、解決方法がわかりませんこの場合のサブ問題。

ソリューションの理解に役立つ説明があれば、感謝します。次のように

はこれまでのところ、私は最適なサブ構造特性を理解する：

例階乗：

ので40、事実（40）の階乗のために、我々は事実を計算することにより、ソリューションを実現することができます（ 39）* 40、など39,38 .... 2 ans我々は、事実（2）が2であることを知っているので、同じ方法で2から40までそれを構築することができます。

しかし、私はLISの面で関係することはできませんよ、それは後で処理できるように、溶液の

完全な説明は、重複部分問題の問題を除いて、いいだろう助けてください。

ありがとうございました。

Answer 1

最適な部分構造を検討する前に、LISの場合のサブ問題は何かを決定する必要があります。のは、この定義を使用してみましょう：長さNの配列a[N]で

部分問題LIS[k]は要素a[k]で正確に終わる最初のインデックスから最長増加部分列の長さを見つけることです。

ここでの違いを理解することが重要である：LIS[k]は最初k要素にLISを解決ではありません。すべてiの場合kまではMax(LIS[i])となります。これは、特定の要素で終わる最長増加部分列の長さです。 Nまでの各iに対して

• ：手でこの定義に

  、それはLISへのソリューションを構築することは容易である

• 設定LIS[i] 1の（最悪の場合には、その数はAです
• 最初の要素からi-1までをjsのように検索すると、a[i] > a[j]とLIS[j]+1 > LIS[i]のようになります。

なお、上記アルゴリズムはO（i）でi以下全てj秒間LIS[j]を部分問題するLIS[i]所与のソリューションに対する解決策を構築することを確認することは容易です。 k-1サブ問題の解からk問題への解を構築することができるので、問題は最適な部分構造を持っています。

注：上記は、バイナリ検索を使用してさらに最適化できます。しかし、サブ問題と最適な基礎構造についての推論は同じです。