Вопросы с тегом «dynamic-programming»

Вопросы о задачах, которые можно решить, комбинируя рекурсивно полученные решения подзадач.

52
Проблема ранца - NP-полная, несмотря на динамическое программирование?

Проблемы с рюкзаком легко решаются динамическим программированием. Динамическое программирование выполняется за полиномиальное время; вот почему мы делаем это, верно? Я читал, что это на самом деле NP-полная проблема, однако это означает, что решить проблему в полиномиальной задаче, вероятно,...

39
Выбор подзадач для динамического программирования

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

33
Есть ли разница между динамическим программированием сверху вниз и снизу вверх?

Есть ли принципиальная разница между динамическим программированием сверху вниз и снизу вверх? В частности, существует ли проблема, которую можно решить снизу вверх, но не сверху вниз? Или подход снизу вверх просто раскручивает повторение подхода сверху...

33
Что такое динамическое программирование?

Извините заранее, если этот вопрос звучит глупо ... Насколько я знаю, построение алгоритма с использованием динамического программирования работает следующим образом: выразить проблему как рекуррентное отношение; Реализуйте рекуррентную связь либо через памятку, либо через восходящий подход....

19
Различие в кейсе при динамическом программировании: пример необходим!

Я работал над динамическим программированием в течение некоторого времени. Канонический способ оценить рекурсию динамического программирования - создать таблицу всех необходимых значений и заполнять ее построчно. См., Например, Cormen, Leiserson и др .: «Введение в алгоритмы» для введения. Я...

19
Чем динамическое программирование отличается от грубой силы

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

16
динамическое программирование упражнений на струнах

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

16
Наибольшая сумма, делимая на n

Я задал этот вопрос на StackOverflow , но я думаю, что это более подходящее место. Это проблема из курса Введение в алгоритмы : У вас есть массив с положительными целыми числами (массив не нужно сортировать или элементы уникальны). Предложите алгоритм , чтобы найти наибольшую сумму элементов,...

14
Памятка без массива

В разделе 15.3 « Элементы динамического программирования» Кормена и др. « Введение в алгоритмы» объясняется запоминание следующим образом: Записанный рекурсивный алгоритм поддерживает запись в таблице для решения каждой подзадачи. Каждая запись таблицы изначально содержит специальное значение,...

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

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

13
Матрица цепочек умножения и возведения в степень

Если у меня есть две матрицы AAA и BВB с размерами 1000×21000×21000\times2 и 2×10002×10002\times1000 , соответственно, и я хочу вычислить (AB)5000(AВ)5000(AB)^{5000} , более эффективно сначала переписать выражение как A(BA)4999BA(ВA)4999ВA(BA)^{4999}B и только потом оценивать численно, потому что...

12
Слово факторизация за

Учитывая две строки S1,S2S1,S2S_1, S_2 , мы пишем S1S2S1S2S_1S_2 для их объединения. Учитывая , строка SSS и целое число k≥1k≥1k\geq 1 , мы будем писать (S)k=SS⋯S(S)k=SS⋯S(S)^k = SS\cdots S для конкатенации kkk копий SSS . Теперь, учитывая строку, мы можем использовать эту запись, чтобы «сжать» ее,...

11
Вариант задачи о ранце

Как бы вы подошли к проблеме ранца в ситуации динамического программирования, если теперь вам нужно ограничить количество предметов в ранце константой ппp ? Это та же самая проблема (максимальный вес , каждый предмет имеет значение и вес ), но вы можете добавить только предмет (ы) в рюкзак и,...

11
Динамическое программирование с большим количеством подзадач

Динамическое программирование с большим количеством подзадач. Поэтому я пытаюсь решить эту проблему с улицы Интервью: Ходьба по сетке (оценка 50 баллов) Вы находитесь в мерной сетке в позиции . Размеры сетки: ). За один шаг вы можете идти на один шаг вперед или назад в любом из измерений. (Так что...

10
Может ли это быть проблемой NP-Complete?

Рассмотрим следующую постановку задачи: Получив начальное число, вы и ваш друг по очереди вычитаете из него идеальный квадрат. Первый, кто доберется до нуля, побеждает. Например: Начальное состояние: 37 Игрок1 вычитает 16. Состояние: 21 Игрок2 вычитает 8. Состояние: 13 Игрок1 вычитает 4. Состояние:...

10
Микрооптимизация для вычисления расстояния редактирования: это правильно?

В Википедии дается реализация восходящей схемы динамического программирования для расстояния редактирования. Это не следует определению полностью; внутренние ячейки вычисляются следующим образом: if s[i] = t[j] then d[i, j] := d[i-1, j-1] // no operation required else d[i, j] := minimum ( d[i-1, j]...

9
Как восстановить лес синтаксических деревьев из вектора Эрли?

Использовать вектор Эрли в качестве распознавателя довольно просто: когда достигается конец строки, вам просто нужно проверить завершенную аксиоматическую постановку, начатую в позиции 0. Если у вас есть хотя бы один, тогда строка принимается. Использование вектора Эрли для восстановления дерева...

9
Нахождение самой длинной повторяющейся подпоследовательности

Учитывая строку , я хотел бы найти самую длинную повторяющуюся (по крайней мере дважды) подпоследовательность. То есть я хотел бы найти строку которая является подпоследовательностью (не обязательно должна быть смежной) такой что . То есть - это строка, половинки которой появляются дважды подряд....

9
Что такое «динамический» в динамическом программировании?

У одного из моих пожилых людей было собеседование, и его спросили, почему это называется динамическим. Он не мог ответить, и после того, как он сдался, интервьюер сказал, что в этом нет ничего динамичного, его просто так называют. В это трудно поверить. Относится ли это к тому, что подзадачи...