如何确定使用动态规划的最长递增子？ [英] How to determine the longest increasing subsequence using dynamic programming?

问题描述

让我们说我有一个整数集。我希望找到一套使用动态规划的最长递增子。这简直是​​练出来的，回顾我的旧笔记从我的算法当然，我似乎不明白这是如何工作。

Let's say I have a set of integers. I want to find the longest increasing subsequence of that set using dynamic programming. This is simply out of practice, reviewing my old notes from my algorithms course, and I don't seem to understand how this works.

推荐答案

OK，我会先介绍最简单的解决方案，这是O（N ^ 2），其中N是集合的大小。此外，还存在一个O（N日志N）的解决方案，我将描述也。此处看起来在一节高效的算法。

OK, I will describe first the simplest solution which is O(N^2), where N is the size of the set. There also exists a O(N log N) solution, which I will describe also. Look here for it at the section Efficient algorithms.

我将假设该阵列的索引是从0到N-1。因此，让我们定义的DP [I]是LIS（最长递增子），该指数i止于元素的长度。为了计算DP [我]大家看看各项指标J＆LT;我和同时检查是否DP [J] + 1> DP [i]和阵列[J] LT;数组[I]（我们希望它是增加）。如果这是真的，我们可以更新当前最佳用于DP [i]于。要找到你可以从DP [0..N-1]。

I will assume the indices of the array are from 0 to N-1. So let's define DP[i] to be the length of the LIS(Longest increasing subsequence) which is ending at element with index i. To compute DP[i] we look at all indices j < i and check both if DP[j] + 1 > DP[i] and array[j] < array[i](we want it to be increasing). If this is true we can update the current optimum for DP[i]. To find the global optimum for the array you can take the maximum value from DP[0..N-1].

int maxLength = 1, bestEnd = 0;
DP[0] = 1;
prev[0] = -1;

for (int i = 1; i < N; i++)
{
   DP[i] = 1;
   prev[i] = -1;

   for (int j = i - 1; j >= 0; j--)
      if (DP[j] + 1 > DP[i] && array[j] < array[i])
      {
         DP[i] = DP[j] + 1;
         prev[i] = j;
      }

   if (DP[i] > maxLength)
   {
      bestEnd = i;
      maxLength = DP[i];
   }
}

我使用数组 $ P $光伏来以后能够找到实际的序列不仅是它的长度。只需使用preV [bestEnd]回去递归从bestEnd在一个循环。 -1值是一个标志停下来。

I use the array prev to be able later to find the actual sequence not only its length. Just go back recursively from bestEnd in a loop using prev[bestEnd]. The -1 value is a sign to stop.

确定，现在到了更有效的 O（N日志N）解决方法：

OK, now to the more efficient O(N log N) solution:

让 S [POS] 被定义为最小的整数，结束长度的递增序列 POS 。

Let S[pos] be defined as the smallest integer that ends an increasing sequence of length pos.

通过每一个整数 X 输入设置现在遍历并执行以下操作：

Now iterate through every integer X of the input set and do the following:

1. 如果 X >在取值，然后追加 X 到取值的结束。这essentialy意味着我们已经找到了新的最大的 LIS 。

1. If X > last element in S, then append X to the end of S. This essentialy means we have found a new largest LIS.

否则找到取值，这是最小的元素＆GT; = 比 X ，并将其更改为 X 。 因为取值排序在任何时候，该元素可以使用二进制搜索中找到日志（N）。

Otherwise find the smallest element in S, which is >= than X, and change it to X. Because S is sorted at any time, the element can be found using binary search in log(N).

总运行时间 - N 整数和二进制搜索为他们每个人 - 的n * log（N）= O（N日志N）

Total runtime - N integers and a binary search for each of them - N * log(N) = O(N log N)

现在让我们做一个真实的例子：

Now let's do a real example:

整数集： 2 6 3 4 1 2 9 5 8

步骤：

0. S = {} - Initialize S to the empty set
1. S = {2} - New largest LIS
2. S = {2, 6} - New largest LIS
3. S = {2, 3} - Changed 6 to 3
4. S = {2, 3, 4} - New largest LIS
5. S = {1, 3, 4} - Changed 2 to 1
6. S = {1, 2, 4} - Changed 3 to 2
7. S = {1, 2, 4, 9} - New largest LIS
8. S = {1, 2, 4, 5} - Changed 9 to 5
9. S = {1, 2, 4, 5, 8} - New largest LIS

因此​​，LIS的长度 5 （大小S）。

要重建的实际 LIS ，我们将再次使用父数组。 让父[I] 是元素的索引我在的predecessor LIS 的元素与索引我。

To reconstruct the actual LIS we will again use a parent array. Let parent[i] be the predecessor of element with index i in the LIS ending at element with index i.

为了让事情变得更简单，我们可以保持在阵列中取值，而不是实际的整数，但其索引（位置）在集合。我们不要让 {1，2，4，5，8} ，但保持 {4，5，3，7，8} 。

To make things simpler, we can keep in the array S, not the actual integers, but their indices(positions) in the set. We do not keep {1, 2, 4, 5, 8}, but keep {4, 5, 3, 7, 8}.

这是输入[4] = 1 ，输入[5] = 2 ，输入[3] = 4 ，输入[7 ] = 5 ，输入[8] = 8

That is input[4] = 1, input[5] = 2, input[3] = 4, input[7] = 5, input[8] = 8.

如果我们正确更新父阵列，实际LIS是：

If we update properly the parent array, the actual LIS is:

input[S[lastElementOfS]], 
input[parent[S[lastElementOfS]]],
input[parent[parent[S[lastElementOfS]]]],
........................................

我们最重要的事情 - 我们如何更新父阵列？有两个选项：

Now to the important thing - how do we update the parent array? There are two options:

1. 如果 X >在取值，然后父[indexX ] = indexLastElement 。这意味着最新元素的父是最后一个元素。我们只是prePEND X 到 S的前端。

1. If X > last element in S, then parent[indexX] = indexLastElement. This means the parent of the newest element is the last element. We just prepend X to the end of S.

否则发现的最小元素的指数取值，这是＆GT; = 比 X ，并将其更改为 X 。在这里，父[indexX] = S [指数 - 1]

Otherwise find the index of the smallest element in S, which is >= than X, and change it to X. Here parent[indexX] = S[index - 1].

这篇关于如何确定使用动态规划的最长递增子？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！