题目分析

汉诺塔是一个经典的递归算法，小伙伴们在学习算法课程时应该接触过这个问题。当时我学习递归的时候，遇到的两个经典问题，一个是斐波那契数列问题，一个就是汉诺塔问题。当然这个问题难度稍微大了一些，当时只需要打印移动的过程，这个题目是要用数组模拟移动的过程。

递归

思考一个问题，如果要将A通过B移动到C，我们应该怎么做？类比于将大象放进冰箱需要几步？

将A中除了最后一个盘子，其他的盘子都放在B中。
将A中最后一个盘子放入C。
将B中所有盘子放入C。

定义：subQuestion(A, B, C, nums)指将A中的nums个盘子在B柱子的帮助下，全部放入到C中。

因此递归的思路就很明确了，**先将A中的盘子除了最后一个，在C的帮助下都放入B，可以表示为subQuestion(A, C, B, nums - 1)。然后将A中剩余的盘子放入C，C.push_back(A.back())，A.pop_back()。最后将B中的所有盘子，在A的帮助下都放入C，此时B中盘子个数为nums - 1，可以表示为subQuestion(B, A, C, nums - 1)**。

其中出口条件是nums = 0时，当nums = 0，不需要任何操作，直接return即可。

算法的**时间复杂度为$O(2^n)$，空间复杂度为$O(n)$**。

其中每次操作都会分裂为两个额外的操作，因此时间复杂度为$O(2^n)$，空间复杂度是递归的栈调用消耗的空间，其中递归的深度最大为n，空间复杂度为$O(n)$

#include<iostream>
#include<vector>

using namespace std;

class Solution {
public:
    void hanota(vector<int>& A, vector<int>& B, vector<int>& C) {
        subQuestion(A, B, C, A.size());
    }

    void subQuestion(vector<int>& A, vector<int>& B, vector<int>& C, int num) {
        if (num == 0) return;
        subQuestion(A, C, B, num - 1);
        C.push_back(A.back());
        A.pop_back();
        subQuestion(B, A, C, num - 1);
    }
};

刷题总结

这个问题时最经典的递归问题，没有接触过的小伙伴可能觉得有些困难，理清楚思想之后还是比较清晰的，希望小伙伴们可以顺利写出来。