[Algorithms] Tower of honoi

Question

Can we solve Towers of honoi with DP? If yes,then what will be time and space complexity?

Comments

time complexityO(2^n) //number of disk moves
space complexityO(1) //number of disks

---

Do this problem exhibit any properties of dynamic programming?I dont think so....there is no polynomial time algo for this (atleast till now) it will be in the order of exponential only.Even if you store every computation in any space it will be useless as you will compute only once and use once.

---

@srestha  space complexity is not O(1) . Since we are using recursion , we have to consider the depth of the recursive stack  which is O(n)  I think .

---

but if there are 3 element , we will go upto depth 3 in stack

if 5 element, we go upto depth 5

Isnot it?