【第三轮】6.30-7.6 CareerCup 3.4

jason51122 发表于 2014-7-7 13:41
Why the space complexity is 2n-1? We have n disks in total and move them within 3 towers. The maxi ...

我的算法中1.disk不占用空间 2. stack中元素的个数相当于递归深度。假定n个disks时的最大递归深度为F(n),那么stack一开始时stack中会有3个operation，分别是将标号1～n-1的disk移到temp、将标号n的disk移到destination、将标号1～n-1的disk移到destination, 所以可以得到最大递归深度 F(n) = F(n-1） + 2 ，即将标号1～n-1的disk移到temp （F(n-1)）和另外两个operation。然后由F(1) = 1 推出F(n) = 2n -1

chouclee 发表于 2014-7-7 20:19
我的算法中1.disk不占用空间 2. stack中元素的个数相当于递归深度。假定n个disks时的最大递归深度为F(n), ...

Got it. Your algorithm saves operations in the stack instead of disks. That's a pretty interesting solution.

【解题思路】
recursion


【时间复杂度】
O(2^n)


【空间复杂度】
O(n)


【gist link】
https://gist.github.com/happyWinner/a1d520505268029829dc

【解题思路】
记得几年前看书的时候遇到过这个问题，当时绞尽脑汁半天最后还是举白旗看的答案
如今再遇此题，答案早已忘光，20分钟写出这个第归方法，小小有点成就感
写第归算法的乐趣在于，思考时候费尽，写出来往往就几行代码
【时间复杂度】
O(2^n)

【空间复杂度】
O(n)

【gist link】
https://gist.github.com/Noahsark/32d622febc477cf7f68c