Сложность для башен Ханоя?
Недавно я решал проблему Ханойских Башен. Я использовал «Разделяй и властвуй» Стратегия для решения этой проблемы. Я разделил основную проблему на три более мелкие подзадачи, и, таким образом, возникла следующая повторяемость.
T(n)=2T(n-1)+1
Решение этого приводит к
O(2^n) [exponential time]
Затем я попытался использовать технику запоминания, чтобы решить ее, но и здесь сложность пространства была экспоненциальной, и куча пространства очень быстро исчерпалась, и проблема все еще была неразрешимой для больших n.
Есть ли способ решить проблему менее чем за экспоненциальное время? В какое время лучше всего решить проблему?