Динамическое программирование - это метод, используемый для решения проблем путем рекурсивного сокращения сложных случаев до простых, до тех пор, пока вы не достигнете случая, достаточно простого для решения «путем проверки».Следовательно, разумный подход ДП к проблеме n-головоломки возможен только в том случае, если на каждом этапе вы можете рассмотреть ход, который уменьшает сложность задачи.
Например, если первый «ход»в n-головоломке всегда превращается в «(n-1) -пазл» (для некоторого конкретного определения «перемещения» и при условии, что (n-1) -пазл имеет смысл), тогда вы можете применить DP, в конце концоврешение "1-головоломки" и составление назад для решения n-головоломки.
Я не знаю ни одного такого процесса упрощения для n-головоломки;и я не могу думать об одном в данный момент.Однако это не значит, что никого не существует.