题解 | #汉诺塔问题#

/*
代码写的有点乱，核心思路就是
记把n个盘子从left->right的步骤为Dp_left_right[n]
首先需要把头上n-1个盘子right->mid，然后把第n个盘子从left->right
最后再把n-1个盘子mid->right.
则有：
Dp_left_right[n] = Dp_left_mid[n-1] + left->right + Dp_mid_right[n-1]
需要注意的是，不管这n个盘子怎么移动，本质上都是从一个from到to，
然后有一个可以操作的space，我们只需要改变这些目标的名字就可以了
假设有一个更换名字的函数f,表达试就变为：
Dp_left_right[n] = f1(Dp_left_right[n-1]) + left->right + f2(Dp_left_right[n-1])
*/
class Solution {
private:
    int num;
    void transform(vector<vector<string>> &dp, string from, string to, string space){
        for(int i=0;i<dp.size();++i){
            for(int j=0;j<dp[0].size();++j){
                if(dp[i][j]=="left"){dp[i][j]=from;continue;}
                if(dp[i][j]=="right"){dp[i][j]=to;continue;}
                if(dp[i][j]=="mid"){dp[i][j]=space;continue;}
            }
        }
    }
    void move(int id, vector<vector<string>> &dp){
        if(id>=num){
            return;
        }
        vector<vector<string>> dp_from_space = dp;
        transform(dp_from_space,"left","mid","right");
        vector<vector<string>> dp_space_to = dp;
        transform(dp_space_to,"mid","right","left");
        dp_from_space.push_back({"left","right"});
        for(auto vec:dp_space_to)dp_from_space.push_back(vec);
        dp = dp_from_space;
        move(id+1,dp);
    }
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param n int整型 
     * @return string字符串vector
     */
    vector<string> getSolution(int n) {
        // write code here
        num = n;
        vector<vector<string>> dp={{"left","right"}};
        move(1,dp);
        vector<string> ans;
        for(auto vec:dp){
            string word = "move from "+ vec[0] + " to " + vec[1]; 
            ans.push_back(word);
        }
        return ans;
    }
};