Gibt es eine Top Down Dynamic Programming-Lösung für Längste steigende Subsequenz?

Question

Ich möchte wissen, wie Sie das LIS eines Arrays mit Top Down Dynamic Programming finden. Gibt es eine solche Lösung? Kannst du mir den Pseudocode geben, um das LIS eines Arrays mit Top Down Dynamic Programming zu finden? Ich kann keins im Internet finden. Alle benutzen Bottom Up.

Answer 1

Sicher. Definieren:

F (n) = längste aufsteigende Teilfolge der Folge 1..n , und die Sequenz muss endet mit dem Element _n

Dann erhalten wir, dass Rekursion Funktion (von oben nach unten):

F (n) = max (len (F (i)) + 1), 0 = i < < n und array [i] < array [n]

So ist die Antwort:

Longest zunehmende Folge von F (1..n)

Mit memoization kommen wir zu diesem Code (Das ist Python, es als Pseudo-Code ist besser):

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]