Я знаю, что каждая программа, которая может быть решена с помощью динамического программирования, может быть решена с помощью рекурсии, но также возможно и наоборот? Если возможно, тогда как будет отличаться временная сложность?Рекурсия и динамическое программирование
это также возможно?
Да.
С другой стороны, если вы на самом деле хотел спросить:
является наоборот тоже верно?
Тогда разумно говорить ответ №. Не все проблемы, которые могут быть решены с помощью рекурсивных алгоритмов, можно разумно решить с помощью динамического программирования. Нам нужно только придумать одну проблему, чтобы выделить это: сортировка. Легко решить проблему сортировки с помощью рекурсивного алгоритма, но, похоже, не существует разумного алгоритма для решения проблемы сортировки с динамическим программированием. К сожалению, мне приходится прибегать к использованию ласкового слова «разумное» здесь, потому что вы могли бы принудительно использовать динамическое программирование каким-то образом, чтобы решить проблему сортировки очень неудобно и неэффективно.
Невозможно ответить на вопрос о временной сложности. Это зависит от проблемы и того, как применимое динамическое программирование будет в решении проблемы.
Если мы хотим найти перестановки строки, которая может быть вычислена с помощью рекурсии. Можно ли решить тот же вопрос с помощью динамического программирования? – Zephyr
Проблема должна иметь два ключевых свойства для динамического программирования, которые могут быть полезны при решении проблемы: перекрывающиеся подзадачи и оптимальная подструктура. Имеют ли проблемы комбинаторной генерации (нахождения перестановок строк) эти два ключевых свойства? – wookie919
У него нет перекрывающихся подпроцессов. Значит, это невозможно решить с помощью динамического программирования? – Zephyr
Динамическое программирование - это компромисс во времени и сложности. Вы храните некоторую информацию в таблицах, поэтому вам не нужно их компрометировать, если вам нужно снова сделать то же самое.
Если ваша проблема естественным образом разлагается на подзадачи, которые часто повторяются, то динамическое программирование является хорошей идеей. С другой стороны, если нет повторяющихся подзадач, тогда нет смысла использовать динамическое программирование.
Не отвечает на вопрос. Вопрос не имеет никакого отношения к тому, когда или нет «нет смысла в использовании динамического программирования». Это теоретический вопрос о том, разрешает ли проблема рекурсия, что она также может быть решена с помощью динамического программирования. – nhouser9
Ну, я так и сказал. Будет ли динамическое программирование работать для общей проблемы рекурсии, зависит от того, нужно ли вам перекомпоновать любые подзадачи во время вычислений. Если повторных подстанций нет, тогда нет никакого коэффициента усиления от динамического программирования. – hugomg
На это нельзя ответить, если вы не скажете, что означает «решение программы с использованием динамического программирования». В общем, это не точно определенная вещь. Например, что означало бы для программы, которая сортирует массив для использования динамического программирования? –
Я попросил его в целом, как печать перестановки строки, которая может быть выполнена с помощью рекурсии. можно ли это сделать с помощью динамического программирования? – Zephyr