【递归搜索回溯专栏】专题一递归：汉诺塔

题目来源

本题来源为：

Leetcode 汉诺塔问题

题目描述

在经典汉诺塔问题中，有 3 根柱子及 N 个不同大小的穿孔圆盘，盘子可以滑入任意一根柱子。一开始，所有盘子自上而下按升序依次套在第一根柱子上(即每一个盘子只能放在更大的盘子上面)。移动圆盘时受到以下限制:

(1) 每次只能移动一个盘子;

(2) 盘子只能从柱子顶端滑出移到下一根柱子;

(3) 盘子只能叠在比它大的盘子上。

请编写程序，用栈将所有盘子从第一根柱子移到最后一根柱子。

你需要原地修改栈。

算法原理

如何解决汉诺塔问题：

在解决汉诺塔问题之前，我们首先要知道应该如何来解决此问题。我们一般采取举例子的方式来发现规律：

1. 当n=1时直接将盘子挪动到C柱子

2. 当n=2的时候，需要先将A柱子的第一个盘子挪动到B柱子，然后在将A柱子的第二个盘子移动到C柱子，最后在将B柱子的盘子移动到C柱子，也就是说我们借助了B柱子来实现将盘子转移的过程。

3. 当n=3时，先将A柱子的第一个盘子和第二个看成一个整体，借助C柱子，使其移动到B柱子**，而这个问题不就是N=2的时候的情况嘛**，此时就可以将第三个盘子移动到C柱子，依次内推，B柱子上的盘子在借助A柱子转移到C柱子上。
   
   到这我们其实就可以发现规律了：
   当为n时，需要借助n-1次，将最底下的盘子移动到C柱子。然后在借助A柱子将B柱子上的盘子移动到C柱子

为什么用递归：

到这一步，我们就可以考虑用递归了。

因为主问题和我们的子问题是一模一样的。

子问题的子问题也是一模一样的。

如何编写递归代码：

1. 重复子问题->函数头：
   
2. 只关心某一个子问题在干什么->函数体的书写：
   
3. 递归的出口：
   当x=1的时候直接转移到Z柱子上。

代码实现

class Solution 
{
public:
    void hanota(vector<int>& A, vector<int>& B, vector<int>& C) 
    {
        //
        dfs(A,B,C,A.size());
    }
    void dfs(vector<int>& a,vector<int>& b,vector<int>& c,int n)
    {
        //递归出口
        if(n==1)
        {
            //直接将A柱子转移到C柱子
            c.push_back(a.back());
            a.pop_back();
            return;
        }
        //函数体
        dfs(a,c,b,n-1);
        c.push_back(a.back());
        a.pop_back();
        dfs(b,a,c,n-1);
    }
};

其实本题有更简单的做法：

既然是转移，那我们可以直接进行转移：

class Solution 
{
public:
    void hanota(vector<int>& A, vector<int>& B, vector<int>& C) 
    {
        //直接转移
        C=A;
    }
};