题解 | #汉诺塔问题#

汉诺塔问题：将n个盘子从left柱，借助mid柱，放至right柱（大的盘子不能放在小的盘子上）

可以分解为以下三个步骤：

1. 把n-1个盘子，从left，借助mid，放至right上
2. 把最大的盘子，从left，放至right上。
3. 把n-1个盘子从mid，借助left，放至right上

tips：经过前两步操作，最大的盘子已经就位，无需移动且对问题不再产生影响。相当于问题已经重置，需要将剩下的n-1个盘子，移动至righ柱子上。盘子均放在mid柱上，相当于初始时的left。

# 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
#
# 
# @param n int整型 
# @return string字符串一维数组
#
class Solution:
    def getSolution(self , n: int) -> List[str]:
        # write code here
        self.ans = []
        self.Hanoi(n, "left", "mid", "right")
        return self.ans
    
    # 定义汉诺塔问题，将n个盘子，从left，借助mid，移动到right上
    def Hanoi(self, n, left, mid, right):
        # 递归的停止条件
        if n == 0:
            return
        else:
            # 1、将n-1个盘子，从left，借助right，移动到mid上
            self.Hanoi(n - 1, left, right, mid)
            # 2、将最大的盘子从left，移动至right
            t = "move from " + left + " to " + right
            self.ans.append(t)
            # 3、把n-1盘子，从mid借助left，移动至right上
            self.Hanoi(n -1, mid, left, right)