Когда вы использовали динамическое программирование на местах?

Question

Когда вы когда-либо непосредственно применяли концепции динамического программирования для решения проблемы в полевых условиях? Иногда неясно, как его можно применять при его использовании для решения выдуманного экземпляра задачи о ранце .

Answer 1

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

Кстати, на странице, на которую вы ссылались, есть список алгоритмов, использующих DP .