• 2 Posts
  • 15 Comments
Joined 1 year ago
cake
Cake day: July 5th, 2023

help-circle












  • I didn’t know the answer either, but usually you can compose solution from solutions of smaller problems.

    solution(0): There are no disks. Nothing to do. solution(n): Let’s see if I can use solution(n-1) here. I’ll use solution(n-1) to move all but last disk A->B, just need to rename the pins. Then move the largest disk A->C. Then use solution(n-1) to move disks B->C by renaming the pins. There we go, we have a stack based solution running in exponential time.

    It’s one of the easiest problem in algorithm design, but running the solution by hand would give you a PTSD.