1D Воспоминание в рекурсивном решении самой длинной нарастающей подпоследовательности

Question

Расчет LIS (самая длинная нарастающая подпоследовательность) в массиве - очень известная проблема динамического программирования. Однако в каждом учебном пособии они сначала показывают рекурсивное решение без использования понятий DP, а затем решают его, применяя Bottom-Up DP (Итеративное решение).

Мой вопрос:

Как мы будем использовать запоминанием в рекурсивного решения сам. Не только памятка, но и воспоминания с использованием 1D массив.

Я провел некоторое исследование, но не нашел ничего подходящего. Хотя есть 2 места, где была запрошена рекурсивная memoization 1 & 2, но решения там, используют 2D Map/Array для memoization.

Как бы то ни было Запоминание решения массивом 1D, дает неправильный. Вот что я сделал:

int lis(int idx, int prev) 
{ 
    if(idx >= N) 
     return 0; 

    if(dp[idx]) 
     return dp[idx]; 

    int best_ans = lis(idx+1, prev); 

    int cur_ans = 0; 
    if(arr[idx] > prev) 
    { 
     cur_ans = 1 + lis(idx+1, arr[idx]); 
    } 
    int ans = max(best_ans, cur_ans); 
    dp[idx] = ans; 
    return ans; 
} 

int main() 
{ 
    // Scan N 
    // Scan arr 

    ans = lis(0, -1)); 
    print ans; 
} 

Хотя я знаю причину, почему это решение дает неправильный вывод, как:

Там может быть более чем одно решение для индекса Давать на основании того, что было предыдущее значение.

Но я все еще хочу знать, как это можно сделать с помощью массива 1D.

Мне интересно знать решение, потому что я прочитал, что каждый DP решение Top-Down можно станут ассоциироваться в снизу вверх и наоборот.

Было бы очень полезно, если бы кто-то мог дать представление о том же.

Заранее спасибо.

Answer 1

Это не может быть сделано, потому что проблема принципиально нуждается в построении 2D-структуры данных.

Подход снизу вверх может обмануть, производя одну строку за время структуры данных. С течением времени он создает структуру 2D-данных, но в любой момент времени вы видите только одно измерение.

Подход сверху вниз должен построить всю структуру данных 2D.

Это фундаментальный компромисс в DP. Обычно проще записывать подход сверху вниз. Но подход «снизу вверх» должен иметь только часть общей структуры данных в любое время и, следовательно, имеет значительно более низкие требования к памяти.