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

Т (п) = 2T (п-1) + 1

Решение этого приводит к

O (2 ^ n) [экспоненциальное время]

Затем я попытался использовать технику запоминания, чтобы решить ее, но и здесь сложность пространства была экспоненциальной, и куча пространства очень быстро исчерпалась, и проблема все еще была неразрешимой для больших n.

Есть ли способ решить проблему менее чем за экспоненциальное время? В какое время лучше всего решить проблему?