是否存在用于最长增长子序列的自顶向下动态规划解决方案？

Question

我想知道如何使用自顶向下动态规划来查找数组的LIS。 是否存在这样的解决方案？你可以给我使用自顶向下动态规划来寻找数组的LIS的伪代码吗？我无法在互联网上找到一个。他们都使用自下而上。

Answer 1

当然。定义：

F（N）=最长递增序列1..N 的序列，序列必须元素结束_ň

然后我们得到的递归功能（自上而下）：

F（N）= MAX（LEN（F（I））+ 1）0 < = I < n和阵列[I] <阵列[n]的

因此，答案是：

F（1..1）

随着memoization的

最长递增子，我们得出这样的代码（这是Python的，它比伪代码更好）：

d = {} 
array = [1, 5, 2, 3, 4, 7, 2] 

def lis(n): 
    if d.get(n) is not None: 
     return d[n] 
    length = 1 
    ret = [array[n]] 
    for i in range(n): 
     if array[n] > array[i] and len(lis(i)) + 1 > length: 
      length = len(lis(i)) + 1 
      ret = lis(i) + [array[n]] 
    d[n] = ret 
    return ret 

def get_ans(): 
    max_length = 0 
    ans = [] 
    for i in range(len(array)): 
     if max_length < len(lis(i)): 
      ans = lis(i) 
      max_length = len(lis(i)) 
    return ans 

print get_ans() # [1, 2, 3, 4, 7]