Ich habe kürzlich das Towers of Hanoi-Problem gelöst. Ich habe eine Strategie zum Teilen und Erobern angewendet, um dieses Problem zu lösen. Ich habe das Hauptproblem in drei kleinere Unterprobleme aufgeteilt und so folgende Wiederholung erzeugt.

T (n) = 2T (n - 1) +1

Dies zu lösen führt zu

O (2 ^ n) [Exponentialzeit]

Dann habe ich versucht, es mit der Memo-Technik zu lösen, aber auch hier war die Raumkomplexität exponentiell und der Heap-Raum sehr bald erschöpft und das Problem war für größere n immer noch unlösbar.

Gibt es eine Möglichkeit, das Problem in weniger als exponentieller Zeit zu lösen? Was ist die beste Zeit, in der das Problem gelöst werden kann?