无法理解最长递增子序列的算法 [英] Unable to understand algorithm for Longest Increasing Sub-sequence

问题描述

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

I have been through many online resources to understand how the problem has the optimal sub-structure, but all in vain, I am unable to comprehend how the solution is obtained by solving smaller sub-problems in this case.

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

I would be thankful if any explanation helps in understanding the solution.

到目前为止，我了解最佳子结构属性如下:

so far, I understand the optimal sub-structure property as follows:

阶乘因子示例:

因此对于阶乘为40的事实(40)，我们可以通过计算事实(39)* 40来实现，对于39,38 .... 2 ans依此类推，因为我们知道事实(2)是2，我们可以用相同的方法将其从2增加到40.

So for a factorial of 40 ,fact(40), we can achieve the solution by calculating fact(39)*40, and so on for 39,38....2 ans as we know that fact(2) is 2 we can build it up from 2 to 40 in the same way.

但是我无法在LIS方面建立联系，请提供帮助

对解决方案的完整说明将是不错的选择，不包括重叠的子问题，因为稍后可以解决此问题.

A full explanation of the solution would be nice, excluding the overlapping subproblems issue, as that can be handled later on.

谢谢.

推荐答案

在考虑最佳子结构之前，对于LIS，您需要确定什么是子问题.让我们使用以下定义:

Before considering optimal substructure, you need to decide what are subproblems in the case of LIS. Let's use this definition:

在长度为N的数组a[N]中，子问题LIS[k]将从初始索引中找到最长递增子序列的长度，该子序列恰好在元素a[k]处结束.

In an array a[N] of length N a subproblem LIS[k] is to find the length of a longest increasing subsequence from the initial index, which ends precisely at the element a[k].

重要的是要了解这里的区别:LIS[k]不是不是对头一个k元素的LIS的解决方案；对于k之前的所有i，该值均为Max(LIS[i]).最长的递增子序列的长度终止于特定元素.

It is important to understand the difference here: LIS[k] is not a solution to LIS on the first k elements; that would be Max(LIS[i]) for all is up to k. It is the length of the longest increasing subsequence that ends at the particular element.

有了这个定义，很容易为LIS构建解决方案:

With this definition in hand, it is easy to construct a solution to LIS:

• 对于每个i至N:
• 将LIS[i]设置为1(在最坏的情况下，数字是1的子序列)
• 从初始元素直到i-1(包括首尾)搜索LIS[j]，查找j，例如a[i] > a[j]和LIS[j]+1 > LIS[i].

• For each i up to N:
• Set LIS[i] to 1 (in the worst case, a number is a subsequence of one)
• Search LIS[j] from the initial element up to i-1, inclusive, for js such that a[i] > a[j], and LIS[j]+1 > LIS[i].

很容易看出，对于O(i)中所有i以下的j子问题LIS[j]，给定子问题LIS[j]的解决方案，上述算法为LIS[i]构造了解决方案.因为我们可以从k-1子问题的解决方案构造一个k问题的解决方案，所以该问题具有最优的子结构.

It is easy to see that the above algorithm constructs a solution to LIS[i] given solutions to subproblems LIS[j] for all js below i in O(i). Since we can construct a solution to a k problem from solutions to k-1 sub-problems, the problem has optimal substructure.

注意:可以使用二进制搜索进一步优化上述内容.不过，关于子问题和最佳子结构的推理仍然相同.

Note: The above can be further optimized by using binary search. The reasoning about subproblem and optimal substructure remains the same, though.

这篇关于无法理解最长递增子序列的算法的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！