题解 | #汉诺塔问题#

若可以完成操作，则必然可以借助mid把所有前n-1个正确放置到mid上，然后把第n个放到right.

这时，mid上有n-1个，left为0，right上为n,可以看成n-1的子问题，只是这时mid为原来的left,

left为原来的mid。

所以可以分为两步：

第一步为借助mid把n-1全放到mid上，然后n直接放到right。

第二步，把mid和left处理方法对调或是swap(mid,left)角色，进行n-1阶的处理即可。

#include <vector>
class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param n int整型 
     * @return string字符串vector
     */
    vector<string> getSolution(int n) {
        process(n);
        return res;
    }
    vector<string> res;
    string tab[4]={"","left","mid","right"};
    void process(int n, int left=1,int mid=2,int right=3) {
        if (n==1) {
            string tmp="move from " + tab[left] + " to " + tab[right];
            res.push_back(tmp);
        }
        else {
            process(n-1, left,right,mid);//先把上面n-1放到mid上
            string tmp="move from " + tab[left] + " to " + tab[right]; //最后n直接放到目标right上
            res.push_back(tmp);
            process(n-1, mid, left, right); // 只剩下n-1个了，只是现在的left和mid角色对调
        }
    }
};