1. 题⽬链接：329.矩阵中的最⻓递增路径
2. 题⽬描述：
3. 解法（暴搜->记忆化搜索）：
算法思路：
这是⼀道递归⽅法的经典题⽬，我们可以先从最简单的情况考虑：
• 假设n=1，只有⼀个盘⼦，很简单，直接把它从A中拿出来，移到C上；
• 如果n=2呢？这时候我们就要借助B了，因为⼩盘⼦必须时刻都在⼤盘⼦上⾯，共需要3步（为 了⽅便叙述，记A中的盘⼦从上到下为1号，2号）：
a. 1号盘⼦放到B上；
b. 2号盘⼦放到C上；
c. 1号盘⼦放到C上。 ⾄此，C中的盘⼦从上到下为1号，2号。
• 如果n>2呢？这是我们需要⽤到n=2时的策略，将A上⾯的两个盘⼦挪到B上，再将最⼤的盘 ⼦挪到C上，最后将B上的⼩盘⼦挪到C上就完成了所有步骤。
例如n=3时如下图：
因为A中最后处理的是最⼤的盘⼦，所以在移动过程中不存在⼤盘⼦在⼩盘⼦上⾯的情况。 则本题可以被解释为：
1. 对于规模为n的问题，我们需要将A柱上的n个盘⼦移动到C柱上。
2. 规模为n的问题可以被拆分为规模为n-1的⼦问题：
a. 将A柱上的上⾯n-1个盘⼦移动到B柱上。
b. 将A柱上的最⼤盘⼦移动到C柱上，然后将B柱上的n-1个盘⼦移动到C柱上。
3. 当问题的规模变为n=1时，即只有⼀个盘⼦时，我们可以直接将其从A柱移动到C柱。
• 需要注意的是，步骤2.b考虑的是总体问题中的⼦问题b情况。在处理⼦问题的⼦问题b时，我们 应该将A柱中的最上⾯的盘⼦移动到C柱，然后再将B柱上的盘⼦移动到C柱。在处理总体问题 的⼦问题b时，A柱中的最⼤盘⼦仍然是最上⾯的盘⼦，因此这种做法是通⽤的。
算法流程：
递归函数设计：void hanotaa(vector& A,vector& B,vector& C,int n)
1. 返回值：⽆；
2. 参数：三个柱⼦上的盘⼦，当前需要处理的盘⼦个数（当前问题规模）。
3. 函数作⽤：将A中的上⾯n个盘⼦挪到C中。
递归函数流程：
1. 当前问题规模为n=1时，直接将A中的最上⾯盘⼦挪到C中并返回；
2. 递归将A中最上⾯的n-1个盘⼦挪到B中；
3. 将A中最上⾯的⼀个盘⼦挪到C中；
4. 将B中上⾯n-1个盘⼦挪到C中。
C++算法代码：
class Solution
{
public:
//将A中的盘子借助B转移到C
void move(vector<int>& a, vector<int>& b, vector<int>& c, int n)
{
if(n==1)
{
//将a中的盘子转移到c上
c.push_back(a.back());
//清除a上的盘子
a.pop_back();
return ;
}
//将A中的盘子借助C转移到B
move(a,c,b,n-1);
//将a中的盘子转移到c上
c.push_back(a.back());
//清除a上的盘子
a.pop_back();
//将B中的盘子借助A转移到C
move(b,a,c,n-1);
}
void hanota(vector<int>& A, vector<int>& B, vector<int>& C)
{
//将A中的盘子借助B转移到C
move(A,B,C,A.size());
}
};Java算法代码：
class Solution
{
public void hanota(List<Integer> a, List<Integer> b, List<Integer> c)
{
dfs(a, b, c, a.size());
}
public void dfs(List<Integer> a, List<Integer> b, List<Integer> c, int n)
{
if (n == 1)
{
c.add(a.remove(a.size() - 1));
return;
}
dfs(a, c, b, n - 1);
c.add(a.remove(a.size() - 1));
dfs(b, a, c, n - 1);
}
}