algorithm - 无法理解最长递增子序列的算法

Question

我已经通过许多在线资源来了解问题如何具有最优子结构，但都是徒劳的，我无法理解在这种情况下如何通过解决更小的子问题来获得解决方案。

如果任何解释有助于理解解决方案，我将不胜感激。

到目前为止，我对最优子结构性质的理解如下:

示例阶乘:

因此对于 40 的阶乘，fact(40)，我们可以通过计算 fact(39)*40 来获得解决方案，对于 39,38....2 我们知道 fact(2)，依此类推是 2 我们可以用同样的方法从 2 增加到 40。

但是我无法在LIS方面进行关联，请帮助

解决方案的完整解释会很好，不包括重叠的子问题问题，因为这可以稍后处理。

谢谢。

Answer 1

序列(问题)的 LIS 可以通过对较小序列(子问题)使用 LIS 来解决，这就是为什么已知它具有最佳子结构的原因。

让我试着解释一下这个例子是如何工作的。让我们取一个由 10 个数字组成的随机序列:

[21, 24, 13, 48, -3, 41, 36, 8, -10, 22]

我们将使用更小的问题(更小的序列)来解决这个问题。在这种情况下，子问题的定义是“以给定元素结尾的最长递增数字序列是什么？”

重要的是要了解此子问题与 LIS 不同 - 子问题具有比原始问题更严格的定义(LIS 不需要在最后一个元素处结束)。

出于可读性目的，我将调用“在给定元素处结束的最长递增子序列”:LIS*。

LIS*与LIS的关系是LIS取LIS*的Max

让我们从一个数字开始。

[21]

以 21 结尾的最长递增子序列是什么？它只是“21”。因此我们序列的长度是 1。

序列:[21]
LIS*: 1
LIS:1

现在，对于第二个元素 (24)，根据定义，我们需要使用已经解决的问题的解决方案。我们将对第一个元素使用 LIS，检查第二个元素是否更大 (a[i] > a[j) 以及是否 LIS[j]+1 > LIS[i]。以 24 结尾的最长递增序列是 '21, 24'，长度为 2。

序列:[21, 24]
LIS*: 2
LIS:2

让我们来看第三个元素 (13)。以 13 结尾的最长递增子序列是什么？好吧，13 小于 21 且小于 24，因此条件 a[i] > a[j] 不满足任何前面的元素。因此，以 13 结尾的最长递增子序列是只是 '13' 并且长度为 1。序列 21,24,13 的 LIS 仍然是 2。

序列:[21, 24, 13]
LIS*: 1
LIS:2

让我们看一下第 4 个元素 (48)。我们知道 3 长度序列的解是 2。我们可以找到满足条件 a[i] > a[j] 和 LIS[j]+ 的前一个元素 (24) 1 > LIS[i]。我们知道前一个元素(较小的问题)的解是 2，因此这里的解是 2+1=3。

序列:[21, 24, 13, 48]
LIS*:3
LIS:3

我们对所有后续元素重复该逻辑。

序列:[21, 24, 13, 48, -3, 41, 36, 8, -10, 22]
LIS*: 1 2 1 3 1 3 3 2 1 3
LIS: 1 2 2 3 3 3 3 3 3 3

如您所见，可以通过查看子问题(较小的序列)获得原始问题(长序列)的解，因此已知该问题具有最优子结构。