题解 | #汉诺塔问题#

经典递归入门题，只需要三步即可。

1. 将left的n-1个盘子通过right移到mid上
2. 将1个盘子从left移到right上
3. 将mid上n-1个盘子通过left移到right上

class Solution {
public:
    vector<string> res;
    vector<string> getSolution(int n) {
        // write code here
        string l="left", m = "mid", r = "right";
        hanoi(l, m, r, n);
        return res;
    }
    // 1. 将left的n-1个盘子通过right移到mid上
    // 2. 将1个盘子从left移到right上
    // 3. 将mid上n-1个盘子通过left移到right上
    void hanoi(string &left, string &mid, string &right, int n) {
        if(n < 1) return ;
        hanoi(left, right, mid, n-1);
        move(left, right);
        hanoi(mid, left, right, n-1);
    }
    void move(string &x, string &y) {
        res.push_back("move from " + x + " to " + y);
    }
};