Я родом из физики, и, следовательно, много математики. Я нахожу легко обнаружить проблемы, хорошо подходящие для рекурсивного / динамического программирования, находя сходства с доказательством по индукции .
В доказательстве по индукции у вас есть две части:
- Вы доказываете, что если что-то верно для итерации N, это также верно для итерации N + 1
- Вы доказываете, что это верно для итерации 1
В рекурсивном программировании / динамическом программировании:
- вы определяете условие выхода (например, вы жестко связываете решение для итерации 1)
- Вы рассчитываете решение для итерации N с учетом решения для итерации N-1
Итак, как ответили другие, это вопрос опыта и выбора подсказок, но вы можете повторно использовать другие навыки, чтобы направлять вас. После этого вам нужно всегда иметь две части, которые я упомянул: если нет, то это не сработает.
Например, чтобы сгенерировать все перестановки набора:
- условие выхода: если у вас есть только один элемент, верните его
- рекурсия: перестановки набора из N элементов - это N наборов перестановок, которые вы получаете, выбирая каждый элемент и комбинируя их со всеми N-1 наборами (многих) перестановок подмножества, которые вы получаете, удаляя элемент.
Я никогда не реализовывал ни одного решателя динамического программирования - я занимался математикой / физикой / числовыми вычислениями, а не CS - до тех пор, пока несколько лет назад я не начал заниматься проблемами Project Euler . Решаемые DP проблемы там (например, 76 , 158 , 161 , 242, но их гораздо больше) оказалось в значительной степени мой любимый вид. Вы определенно становитесь лучше в поиске, когда это будет полезная техника: в основном ищите вещи, которые, кажется, могут быть решены с помощью какого-то рекурсивного подхода «разделяй и властвуй», где также можно приручить взрыв путей, нуждающихся быть изученным путем распознавания повторяющихся подзадач и повторного использования ранее вычисленных результатов; способность определить минимальный вектор состояния, о котором следует помнить - и какую несущественную «историю» можно стереть - является решающим шагом.
источник