Здравствуйте, Буравчик, Вы писали:
Б>Почему ты их разделяешь? Решение со стеком это и есть DP. И рекурсия с мемоизацией тоже DP.
В моем понимании классическое динамическое программирование — это такой подход, когда в простейшем случае решение можно получить, последовательно заполняя таблицу. По крайней мере, такое мнение мне где-то попадалось.
Re[11]: Принудительный выход из рекурсии в случае, если отве
Здравствуйте, Lazytech, Вы писали:
L>В моем понимании классическое динамическое программирование — это такой подход, когда в простейшем случае решение можно получить, последовательно заполняя таблицу. По крайней мере, такое мнение мне где-то попадалось.
Так все они заполняют таблицу, но:
1. Во-первых, таблицу можно заполнять не полностью, а только те клетки, которые нужны.
2. Во-вторых, не обязательно хранить всю таблицу, достаточно только какие-то последние клетки, необходимые для дальнейших расчетов.
3. В-третьих, не обязательно заполнять таблицу по-порядку.
За счет первого и третьего пункта достигается линейность на простых строках. За счет второго достигается экономия памяти.
Алгоритм со стеком использует все три пункта.
— рассматривает только те варианты, в которые смогли попасть
— удаляет из стека варианты, которые уже были обработаны
— порядок заполнения таблицы определяется верхушкой стека
Алгоритм с рекурсия+мемоизацией
— не использует второй пункт, т.к. хранит в кэше даже те клетки, которые не нужны.
— но при этом использует первый и третий пункт
Твой алгоритм DP не использует ни одного пункта, поэтому он никогда не будет линейным, но максимум будет ограничен размером таблицы — O(M*N), как по времени, так и по памяти.
P.S. Может у меня слишком общий взгляд на динамическое программирование, но я все же считаю это DP
Здравствуйте, vsb, Вы писали:
vsb>Есть забавный способ принудительного выхода из рекурсии — кинуть исключение с результатом.
А лучше развернуть рекурсию в цикл со стеком
... << RSDN@Home 1.3.110 alpha 5 rev. 62>>
Re[3]: Принудительный выход из рекурсии в случае, если ответ
Здравствуйте, CreatorCray, Вы писали:
vsb>>Есть забавный способ принудительного выхода из рекурсии — кинуть исключение с результатом. CC>А лучше развернуть рекурсию в цикл со стеком
Оно-то всегда лучше, но не проще. По-хорошему все эти проблемы с маленькими стеками от несовершенства технологии и должны решаться на уровне компилятора/процессора, а не вручную программистом. Вроде в Go стек условно бесконечный (пока памяти хватает).
Здравствуйте, vsb, Вы писали:
vsb>Оно-то всегда лучше, но не проще.
Почему?
Вместо локальных переиенных на стеке — поля в структуре. Вместо рекурсивного вызова — push в свой стек а код в цикле работает со структурой что на самой вершине стека. Выход из рекурсивной фукнции — просто pop из стека.
vsb> По-хорошему все эти проблемы с маленькими стеками от несовершенства технологии и должны решаться на уровне компилятора/процессора
Нет.
vsb> а не вручную программистом. Вроде в Go стек условно бесконечный (пока памяти хватает).
Не в го в принципе можно сделать так же. Guard page нужна как раз для того, чтобы ловить вот таких вот зациклившихся рекурсивных.
... << RSDN@Home 1.3.110 alpha 5 rev. 62>>
Re[3]: Принудительный выход из рекурсии в случае, если ответ
Здравствуйте, σ, Вы писали:
L>>А как иначе решать такие задачи? Из альтернативных подходов могу назвать только лишь динамическое программирование σ>В каком смысле динамичесткое программирование это альтернативный подход к рекурсии? Это ортогональные вещи.
Я вообще не то, чтобы знаю много подходов к решению задач.
Re[5]: Принудительный выход из рекурсии в случае, если ответ