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

Question

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

Answer 1

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

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