Существует ли решение для динамического программирования сверху вниз для наиболее долгого возрастания подпоследовательности?

Question

Я хочу знать, как найти LIS массива, используя динамическое программирование сверху вниз. Существует ли такое решение? Можете ли вы дать мне псевдокод для поиска LIS массива с использованием динамического программирования сверху вниз? Я не могу найти его в Интернете. Все они используют Bottom Up.

Answer 1

Несомненно. Определение:

F (п) = длинный возрастающую подпоследовательность последовательности 1..n , и последовательность сусло заканчивается элементом _п

Тогда мы получим, что функция рекурсии (сверху вниз):

Р (п) = тах (LEN (F (я)) + 1), 0 = < < я п и массив [я] < массив [п]

Так что ответ:

Серия увеличение подпоследовательность F (1..n)

С 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]