Динамическое программирование: может ли рекурсия с мемоизацией работать с любым рекурсивным решением или только с решениями в определенных форматах?

Я читаю о динамическом программировании и пытаюсь решить проблему самой длинной возрастающей подпоследовательности.

Я попытался придумать метод грубой рекурсии, в котором я генерировал все возможные возрастающие подпоследовательности и проверял, какая из них самая длинная.

private int lis(int[] arr, int k, List<Integer> curr){
    int ans = 0;
    for(int i=k;i<arr.length;i++){
        if(!curr.isEmpty() && arr[i]<=curr.get(curr.size()-1)){
            continue;
        }
        curr.add(arr[i]);
        ans = Math.max(ans, curr.size());
        ans = Math.max(ans,lis(arr,i+1,curr));
        curr.remove(curr.size()-1);
    }
    return ans;
}

Здесь arr — входной массив, k — 0, а curr — список, в котором я храню текущую возрастающую подпоследовательность, ans — глобальная переменная, которая ведет подсчет самой длинной возрастающей подпоследовательности. Я получаю TLE для этого решения, которое ожидается.

Я знаю, что это не самый эффективный подход, так как я использую список для отслеживания элементов, и проблема может быть решена без него. Но я все еще пытался применить мемоизацию к этому коду в качестве упражнения.

Я пытаюсь понять, можно ли мемоизацию применить к любому рекурсивному методу грубой силы (или для этого требуется, чтобы рекурсивное решение было в определенном формате, поскольку существует несколько типов рекурсии, таких как хвостовая рекурсия и т. д.)< /эм>? Если нет, то каким свойствам он должен удовлетворять?

Можно ли применить мемоизацию к приведенному выше алгоритму, чтобы заставить его работать?


recursion algorithm dynamic-programming lis
person varunkr    schedule 05.03.2021    source источник

Ответы (1)


arrow_upward
1
arrow_downward

Мемоизацию можно выполнять, если вы можете создать структуру поиска, которая будет распознавать, совпадают ли аргументы, чтобы вы знали, когда вернуть предыдущий результат.

В Python tuple похож на list, за исключением того, что он является неизменяемым и хешируемым, поэтому его можно использовать в словаре. В других языках вам обычно приходится делать гораздо больше работы, чтобы создать поиск на основе элементов. Какая это работа, зависит от языка. Наиболее распространенным запасным вариантом является создание строкового представления ваших аргументов.

person btilly    schedule 05.03.2021