是否存在用於最長增長子序列的自頂向下動態規劃解決方案？

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]