無法理解最長增加子序列的算法

我已經通過許多在線資源來了解問題是如何具有最佳子結構的，但都是徒勞的，我無法理解如何通過解決更小的問題來獲得解決方案在這種情況下的子問題。無法理解最長增加子序列的算法

如果有任何解釋有助於理解解決方案，我會很感激。

到目前爲止，我理解最佳子結構性質如下：

例階乘：

所以對於40階乘，事實（40），就可以實現通過計算實際上溶液（ 39）* 40，依此類推爲39,38 .... 2，因爲我們知道事實（2）是2，所以我們可以用相同的方法從2到40增加它。

但我不能夠在LIS的方面聯繫，請幫助

解決方案的完整解釋將是很好的，不重疊的子問題的問題，因爲這可以在以後處理。

謝謝。

來源

2017-04-05 Hiresh

你好，Hiresh - 偶然，你是否會混淆遞歸和LIS？通常，LIS算法（可能是遞歸的）涉及一個序列作爲輸入。（通常用於排序，以確定O）。給出的因子例子是遞歸。 – John

嗨，約翰，儘管這個例子是遞歸的，但我認爲它有一個最佳的子結構屬性，因爲小問題被用來建立最終的問題，如果我錯了，請糾正我。 – Hiresh

請參閱下面的答案 - N！的問題，其最佳子結構是N的定義！（以及派生的序列）產生一個長度爲N的LIS。再次，爲了不同的目的，另一個不同的問題。 – John

在考慮最佳子結構之前，您需要確定在LIS情況下哪些是子問題。讓我們使用這樣的定義：

在長度N陣列a[N]一個子問題LIS[k]是從初始索引，這在元件a[k]結束精確地找到最長遞增子的長度。

瞭解這裏的區別是很重要的：LIS[k]是不解決LIS第一k元素;那將是Max(LIS[i])所有i s高達k。它是在特定元素結束時間最長的子序列的長度。

利用這個定義在手，很容易構建一個解決LIS：

對於每個i高達N：
集LIS[i]爲1（在最壞情況下，一個數字是一子序列）
搜索LIS[j]從最初的元素到i-1，包括j，使得a[i] > a[j]和LIS[j]+1 > LIS[i]。

這是很容易看到的是，上述算法構造解決LIS[i]給出的解決方案在O（i）至子問題LIS[j]所有j S下方i。由於我們可以從子問題的解決方案構建解決方案以解決k問題，因此問題具有最佳的子結構。

注意：以上可以通過使用二進制搜索進一步優化。儘管如此，關於子問題和最佳子結構的推理仍然是一樣的。

來源

2017-04-05 13:48:32 dasblinkenlight

我想要求@dasblinkenlight來[http://stackoverflow.com/questions/43236912/how-does-finding-a-longest-increasing-subsequence-that-ends-with-a-particular-el](answer這，這將最終爲我解決問題） – Hiresh

無法理解最長增加子序列的算法

回答

相關問題