最長是如何增加子序列DAG中最長路徑的特例？

Question

我在「Hitchhiker的算法指南」中閱讀了這個說法。但是，我無法將其視爲LIS問題，我們所有的都是一系列數字。我如何將它作爲圖形問題進行調整？

Answer 1

想象一下二維網格的問題。你在左下方，你需要到達右上方。你能想象一個非循環的DAG出於這個方案嗎？

現在想象一些廣場是被禁止的。禁止正方形可能會導致「鎖定」（您可能會發現自己被困住），現在選擇哪條路徑遵循實際上很重要。 就圖形而言，你可以想到禁止正方形爲刪除頂點，你的目標是從根到一個特定節點（接收器）。

現在讓我們回到LIS。在解決LIS時，你實際需要做的是決定你會選擇哪一個號碼，哪一個你不會。限制是，每當你選擇一個號碼，你不能挑選任何數字，這是較小比這一個（你按順序選擇數字）。

現在我們可以混合使用這兩種東西。想象一下，你會用你的數字序列建立一個圖表：

• 每個數字都是一個節點。
• 編號節點A具有與數B節點當且僅當一個邊緣
  • B來到A之後的序列
  • 乙於大於A的值
• 有一個特殊的節點端
• 每個節點都有一個邊緣到端

此圖上的每條路徑都是有效的遞增子序列。找到LIS的問題現在是在該圖上找到最長路徑的問題。

Answer 2

如果我們有一個數字數組，例如說1，5，4，8。我們可以像下面這樣構建一個DAG。

• 將每個數字添加爲頂點。
• 對於每個數字頂點，將權重1的輸出邊添加到後面的所有更大數。
• 向所有數字頂點添加一個節點S，該節點具有權重0的輸出邊。
• 添加一個節點E，該節點具有來自所有數字頂點的權重爲0的傳入邊。

因此，最長增加的子序列問題變成從S到E問題的最長路徑。