Re[10]: Принудительный выход из рекурсии в случае, если ответ уже найден
От: Lazytech Ниоткуда  
Дата: 22.11.20 10:12
Оценка:
Здравствуйте, Буравчик, Вы писали:

Б>Почему ты их разделяешь? Решение со стеком это и есть DP. И рекурсия с мемоизацией тоже DP.


В моем понимании классическое динамическое программирование — это такой подход, когда в простейшем случае решение можно получить, последовательно заполняя таблицу. По крайней мере, такое мнение мне где-то попадалось.
Re[11]: Принудительный выход из рекурсии в случае, если отве
От: Буравчик Россия  
Дата: 22.11.20 10:27
Оценка: 9 (1)
Здравствуйте, Lazytech, Вы писали:

L>В моем понимании классическое динамическое программирование — это такой подход, когда в простейшем случае решение можно получить, последовательно заполняя таблицу. По крайней мере, такое мнение мне где-то попадалось.


Так все они заполняют таблицу, но:
1. Во-первых, таблицу можно заполнять не полностью, а только те клетки, которые нужны.
2. Во-вторых, не обязательно хранить всю таблицу, достаточно только какие-то последние клетки, необходимые для дальнейших расчетов.
3. В-третьих, не обязательно заполнять таблицу по-порядку.

За счет первого и третьего пункта достигается линейность на простых строках. За счет второго достигается экономия памяти.

Алгоритм со стеком использует все три пункта.
— рассматривает только те варианты, в которые смогли попасть
— удаляет из стека варианты, которые уже были обработаны
— порядок заполнения таблицы определяется верхушкой стека

Алгоритм с рекурсия+мемоизацией
— не использует второй пункт, т.к. хранит в кэше даже те клетки, которые не нужны.
— но при этом использует первый и третий пункт

Твой алгоритм DP не использует ни одного пункта, поэтому он никогда не будет линейным, но максимум будет ограничен размером таблицы — O(M*N), как по времени, так и по памяти.

P.S. Может у меня слишком общий взгляд на динамическое программирование, но я все же считаю это DP
Best regards, Буравчик
Отредактировано 22.11.2020 10:28 Буравчик . Предыдущая версия .
Re: Принудительный выход из рекурсии в случае, если ответ уже найден
От: Nuzhny Россия https://github.com/Nuzhny007
Дата: 13.02.21 07:47
Оценка: :))
Здравствуйте, Lazytech, Вы писали:

L>Опять я со своими нескончаемыми дилетантскими вопросами...


Увидел видео и сразу подумал о тебе:
  Видео
Re[2]: Принудительный выход из рекурсии в случае, если ответ
От: Михaил  
Дата: 13.02.21 08:29
Оценка: :)
Здравствуйте, Nuzhny, Вы писали:

N>



Увидел это видео, и сразу подумал об этом:
  Скрытый текст
https://www.youtube.com/watch?v=8DKaXwCSgow
Отредактировано 13.02.2021 8:32 Михaил . Предыдущая версия . Еще …
Отредактировано 13.02.2021 8:30 Михaил . Предыдущая версия .
Отредактировано 13.02.2021 8:30 Михaил . Предыдущая версия .
Re[2]: Принудительный выход из рекурсии в случае, если ответ уж
От: CreatorCray  
Дата: 13.02.21 11:56
Оценка:
Здравствуйте, vsb, Вы писали:

vsb>Есть забавный способ принудительного выхода из рекурсии — кинуть исключение с результатом.

А лучше развернуть рекурсию в цикл со стеком
... << RSDN@Home 1.3.110 alpha 5 rev. 62>>
Re[3]: Принудительный выход из рекурсии в случае, если ответ
От: vsb Казахстан  
Дата: 13.02.21 11:57
Оценка:
Здравствуйте, CreatorCray, Вы писали:

vsb>>Есть забавный способ принудительного выхода из рекурсии — кинуть исключение с результатом.

CC>А лучше развернуть рекурсию в цикл со стеком

Оно-то всегда лучше, но не проще. По-хорошему все эти проблемы с маленькими стеками от несовершенства технологии и должны решаться на уровне компилятора/процессора, а не вручную программистом. Вроде в Go стек условно бесконечный (пока памяти хватает).
Отредактировано 13.02.2021 11:58 vsb . Предыдущая версия .
Re[4]: Принудительный выход из рекурсии в случае, если ответ
От: CreatorCray  
Дата: 14.02.21 00:49
Оценка:
Здравствуйте, vsb, Вы писали:

vsb>Оно-то всегда лучше, но не проще.

Почему?
Вместо локальных переиенных на стеке — поля в структуре. Вместо рекурсивного вызова — push в свой стек а код в цикле работает со структурой что на самой вершине стека. Выход из рекурсивной фукнции — просто pop из стека.

vsb> По-хорошему все эти проблемы с маленькими стеками от несовершенства технологии и должны решаться на уровне компилятора/процессора

Нет.

vsb> а не вручную программистом. Вроде в Go стек условно бесконечный (пока памяти хватает).

Не в го в принципе можно сделать так же. Guard page нужна как раз для того, чтобы ловить вот таких вот зациклившихся рекурсивных.
... << RSDN@Home 1.3.110 alpha 5 rev. 62>>
Re[3]: Принудительный выход из рекурсии в случае, если ответ
От: σ  
Дата: 14.02.21 12:09
Оценка:
_>>А зачем понадобилась рекурсия?

L>А как иначе решать такие задачи? Из альтернативных подходов могу назвать только лишь динамическое программирование


В каком смысле динамичесткое программирование это альтернативный подход к рекурсии? Это ортогональные вещи.
Re[4]: Принудительный выход из рекурсии в случае, если ответ
От: Lazytech Ниоткуда  
Дата: 14.02.21 13:30
Оценка:
Здравствуйте, σ, Вы писали:

L>>А как иначе решать такие задачи? Из альтернативных подходов могу назвать только лишь динамическое программирование

σ>В каком смысле динамичесткое программирование это альтернативный подход к рекурсии? Это ортогональные вещи.

Я вообще не то, чтобы знаю много подходов к решению задач.
Re[5]: Принудительный выход из рекурсии в случае, если ответ
От: σ  
Дата: 16.02.21 12:54
Оценка: :)
L>Я вообще не то, чтобы знаю много подходов к решению задач.
Я тоже
Подождите ...
Wait...
Пока на собственное сообщение не было ответов, его можно удалить.