logo标签列表

如何使用动态规划确定最长递增子序列？

algorithmcomputer-sciencedynamic-programmingmemoizationlis
235
12
关于 DP 解法，我发现很惊讶没有人提到一个事实，即LIS 可以简化为 LCS。 - Salvador Dali
非常好地解释了[LIS]（https://leetcode.com/problems/longest-increasing-subsequence/discuss/1326308/C%2B%2BPython-DP-Binary-Search-BIT-Solutions-Picture-explain-O(NlogN)）。 - Sumit
21个回答
0
使用动态规划[方法1]，可以在theta(n^2)的时间内解决这个问题，以下是代码。
def lis_dp(array):
    alias = [1] * len(array)
    for i in range(1, len(array)):
        for j in range(0, i):
            if array[i] > array[j]:
                alias[i] = max(alias[i], alias[j] + 1)

    output = max(alias)
    return output


arr = [4, 10, 6, 5, 8, 11, 2, 20]
output = lis_dp(array=arr)
print(output)
方法一时间复杂度分析：由于此代码中使用了两个for循环，因此时间复杂度为theta(n^2)。 第二种方法：使用二分查找 这个问题可以在theta(nlog(n))的时间内解决。 理论： 构建尾数组，并且尾数组的长度就是答案。 tail[i]存储着LIS（最长递增子序列）长度为(i + 1)时的最小可能尾值，其中i的范围为(0, n)，n是给定数组的长度。 创建尾数组时的两个条件 条件1：如果要插入到尾数组中的下一个元素大于前一个元素，则将该元素追加到尾部。 条件2：如果要插入到尾数组中的下一个元素小于前一个元素，则将其替换为左侧最接近它的元素。 特殊情况 情况1：如果我们有按降序排列的数组，则输出为1。 情况2：如果我们有按升序排列的数组，则输出为数组的长度。
注意：无论是动态规划还是二分查找方法，边界情况都保持不变。
让我们来看一下第二种方法的代码。
def ceil_idx(tail, x):
    l = 0
    r = len(tail) - 1
    while r > l:
      m = l + (r - l)//2
      if tail[m] >= x:
        r = m
      else:
        l = m + 1
    return r


def lis_bs(array):
    n = len(array)
    tail = [array[0]]

    for i in range(1, n):
         # condition 1: If the next element to be inserted in the tail array is greater than previous one, then element is appended.
       if array[i] > tail[-1]:
         tail.append(array[i])
       else:
         # condition 2: If the next element to be inserted in the tail array is smaller than previous element then it will replace it ceiling to its left.
         c = ceil_idx(tail, array[i])
         tail[c] = array[i]

    return len(tail)


arr = [4, 10, 6, 5, 8, 11, 2, 20]
output_lis = lis_bs(array=arr)
print(output_lis)

第二种方法的时间复杂度分析

由于存在一个循环，它运行到数组的长度，因此需要 theta(n) 的时间，并且在这个循环内部还有另一个函数运行，即二分查找（天花板函数），它需要 log(n) 的时间，因此总共需要 nlog(n) 的时间。

网页内容由stack overflow 提供, 点击上面的
可以查看英文原文，
原文链接