C++ 递归实战：汉诺塔问题详解

汉诺塔是学习递归算法的必经之路。这道题的核心不在于如何一步步搬动盘子，而在于如何将复杂的大问题拆解为简单的子问题。

假设我们有三根柱子 A、B、C，初始时 A 上有 n 个盘子。我们的目标是将所有盘子移到 C 上，且过程中大盘子不能压在小盘子上。

思考一下 n=1 的情况，直接从 A 移到 C 即可。 如果是 n=2，先把上面的小盘移到 B，大盘移到 C，再把小盘从 B 移到 C。 推广到 n，策略就很清晰了：

1. 把 A 上的 n-1 个盘子借助 C 移到 B；
2. 把 A 上剩下的最大盘子直接移到 C；
3. 把 B 上的 n-1 个盘子借助 A 移到 C。

这就是递归的本质：用同样的逻辑解决规模更小的同类问题。

下面是具体的 C++ 实现。这里使用 DFS 模拟移动过程，参数中动态调整辅助柱和目标柱的角色，确保逻辑通用。

class Solution {
public:
    // 辅助函数：将 n 个盘子从 src 移到 dst，aux 作为辅助
    void dfs(vector<int>& src, vector<int>& aux, vector<int>& dst, int n) {
        if (n == 1) {
            // 只有一个盘子时，直接移动
            dst.push_back(src.back());
            src.pop_back();
            return;
        }
        // 1. 将 n-1 个盘子从 src 移到 aux
        dfs(src, dst, aux, n - 1);
        // 2. 将最大的盘子从 src 移到 dst
        dst.push_back(src.back());
        src.pop_back();
        // 3. 将 n-1 个盘子从 aux 移到 dst
        dfs(aux, src, dst, n - 1);
    }

    void hanota(vector<int>& A, vector<int>& B, vector<int>& C) {
        int n = A.size();
        dfs(A, B, C, n);
    }
};