我可以解釋如何使用最佳子結構來找到此幻燈片中最長的子序列？

我正在學習如何在目前的算法類中找到最佳解決方案，其中一個主題是找出問題中的最佳子結構。我可以解釋如何使用最佳子結構來找到此幻燈片中最長的子序列？

我對此的理解到目前爲止，我們看到如果我們能找到一個大小爲n的問題的最佳解決方案。如果可以，那麼我們將問題的大小增加1，所以它是n + 1。如果n + 1的最優解包括n的整個最優解和+1引入的新解，那麼我們有最優的子結構。

我給了一個使用最佳子結構的例子來找到給定一組數字的最長增加的子序列。這顯示在PowerPoint幻燈片的位置：

有人可以給我在幻燈片的底部解釋的符號，並給我一個證明，這個問題可以用最優子解決？

2016-08-22 jarrad_obrien

下（ⅰ）是指一組與當前索引i這樣的左側在S位置j的那個S _Ĵ是少於一_我。換句話說，元素S _j和S _i即使在它們之間可能存在其他元素，但依次遞增。
與左邊的括號表達解釋了我們如何構建答案：
1. 第一行說，如果設定的下限（i）是空的（，就是s _我是序列中的最大數量，以便那麼答案是1.這是基本情況：一個數字被視爲一個元素序列
2. 第二行說如果Lower（i）不是空的，那麼我們從中選擇最大元素，並且加1.換句話說，我們看數字S _i的左邊另一個數字S _j小於S _i，並結束Lower（i）中最長的遞增子序列。

所有這一切都寫這六條線的僞碼的令人難以置信的很長的路要走：

L[0] = 1 
for i = 1..N 
    L[i] = 1 
    for j = i..0 
     if S[i] > S[j] // Member of Lower(i) ? 
      L[i] = MAX(L[i], L[j]+1)

來源

2016-08-22 08:42:53 dasblinkenlight

只需添加到@dasblinkenlight答案：

這是一個迭代的方法基於最優子結構，因爲在任何給定迭代i，我們將計算結束於索引i的最長增加子序列的長度。因此，當我們達到這個迭代時，對於任何索引j < i已經建立了所有相應的LIS。使用這些信息，我們找到索引i, i+1等的答案。現在最初的問題是要求LIS，但它必須有一個結束索引，所以在所有索引中取得最大LIS就足夠了。

這種方法與Mathematical Induction和相當寬泛的編程/算法方法Dynamic Programming有很強的相關性。

P.S.

存在另一個稍微複雜的方法，它允許使用二分搜索以更高效的方式計算LIS。當幻燈片中的算法也存在時，該算法爲O(n^2)，算法也爲。

來源

2016-08-22 09:14:45 Yerken

我可以解釋如何使用最佳子結構來找到此幻燈片中最長的子序列？

回答

相關問題