题解 | 汉诺塔问题

#
# 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
#
# 
# @param n int整型 
# @return string字符串一维数组
#
class Solution:
    def getSolution(self , n: int) -> List[str]:
        # write code here
        #(n,0,0) -> (0,0,n)

        # if n==1:
        #     print('move from left to right')
        # elif n==2:
        #     print('move from left to mid')
        #     print('move from left to right')
        #     print('move from mid to right')
        # elif n==3:
        #     print('move from left to right')
        #     print('move from left to mid')
        #     print('move from right to mid')
        #     print('move from left to right')
        # #move two disks from mid to right (just like n==2, consider mid as left, left as mid)
        # #insight: 先把上面的n-1个盘子移动到 mid，最大的盘子移动到 right
        moves=[]
        def move(num,s, t, temp):
            if num==1:
                moves.append(f'move from {s} to {t}')
            else:
                move(num-1,s,temp,t)
                moves.append(f'move from {s} to {t}')
                move(num-1,temp,t,s)
        move(n,'left','right','mid')
        return moves

• 第一步：将 n-1 个盘子从 left 移动到 mid（借助 right）。

• 第二步：将最大的盘子从 left 移动到 right。

• 第三步：将 n-1 个盘子从 mid 移动到 right（借助 left）。