递归搜索与回溯算法

名词解释

递归

在解决⼀个规模为n的问题时，如果满⾜以下条件，我们可以使⽤递归来解决：

a. 问题可以被划分为规模更⼩的⼦问题，并且这些⼦问题具有与原问题相同的解决⽅法。

b. 当我们知道规模更⼩的⼦问题（规模为n-1）的解时，我们可以直接计算出规模为n的问题 的解。

c. 存在⼀种简单情况，或者说当问题的规模⾜够⼩时，我们可以直接求解问题。

⼀般的递归求解过程如下：

a. 验证是否满⾜简单情况。

b. 假设较⼩规模的问题已经解决，解决当前问题。

汉诺塔问题

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

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

你需要原地修改栈。

示例1:

 输入：A = [2, 1, 0], B = [], C = []输出：C = [2, 1, 0]

示例2:

 输入：A = [1, 0], B = [], C = []输出：C = [1, 0]

提示:

1. A中盘子的数目不大于14个。

解法（递归）：

算法思路：

这是⼀道递归⽅法的经典题⽬，我们可以先从最简单的情况考虑：

• 假设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上就完成了所有步骤。

因为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 dfs(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中。

代码如下：

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){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);}
};

合并两个有序链表

将两个升序链表合并为一个新的 升序 链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。

示例 1：

输入：l1 = [1,2,4], l2 = [1,3,4]
输出：[1,1,2,3,4,4]

示例 2：

输入：l1 = [], l2 = []
输出：[]

示例 3：

输入：l1 = [], l2 = [0]
输出：[0]

解法（递归）：

算法思路：

1. 递归函数的含义：交给你两个链表的头结点，你帮我把它们合并起来，并且返回合并后的头结点；

2. 函数体：选择两个头结点中较⼩的结点作为最终合并后的头结点，然后将剩下的链表交给递归函数 去处理；

3. 递归出⼝：当某⼀个链表为空的时候，返回另外⼀个链表。

代码如下：

/*** Definition for singly-linked list.* struct ListNode {*     int val;*     ListNode *next;*     ListNode() : val(0), next(nullptr) {}*     ListNode(int x) : val(x), next(nullptr) {}*     ListNode(int x, ListNode *next) : val(x), next(next) {}* };*/
class Solution 
{
public:ListNode* mergeTwoLists(ListNode* list1, ListNode* list2) {if(list1==nullptr) return list2;if(list2==nullptr) return list1;if(list1->val<list2->val){list1->next=mergeTwoLists(list1->next,list2);return list1;}else{list2->next=mergeTwoLists(list1,list2->next);return list2;}}};