为了准备今年的秋招，最近报了极客大学算法训练营的线上学习班。本周学习的内容是递归、分治和回溯。这些内容我之前在本科学习算法和数据结构的时候都曾学过。但是我从来没有真正掌握，对这些算法属于一知半解的状态。但既然花钱购买了课程，这次我一定要攻克这些算法。
具体做的第一步是先看视频，听听主讲人覃超老师对于这些算法的讲解以及如何运用这些算法解决算法题。针对递归算法，课程中覃超老师总结了解决递归问题的四个步骤：
1. terminator(递归终止条件)
2. process current level logic(处理当前层逻辑)
3. drill down(递归，进入下一层)
4. reverse state(恢复当前层的状态，可选)
这四个步骤就是“套路”。真正的高手做事的时候都是有各种套路的，这些套路或者是自己总结，或者是从其他高手身上习得。对我来说，学习了这个解题框架后，心里就有谱了，无论是自己做算法题还是看别人的题解，都轻松了许多，不在是以前抓瞎的状态了。
这四个步骤中最重要的是步骤1：terminator（终止条件），如果没有这个步骤，递归就会陷入死循环！虽然覃超老师在讲解题目时反复强调一定要记得写终止条件，但是我自己在做题的过程中仍然有几次忘了写终止条件的情况。所以光听不练是没用的，你以为自己懂了，不会犯错了，但现实往往是一实践马上就犯错！一定要自己练习犯过错误后印象才会深刻，在到了几次错误后，我慢慢养成了每次首先思考终止条件的习惯。
此外还需要提一下的是步骤4：reverse state（状态恢复）。这个步骤并不是所有的递归程序都必须的，但是在回溯算法中确实必须的。具体情况需要看你传入的参数，以及在递归体中是如何进行判断的。比如在Leetcode中的“括号生成”问题中，我们可以通过传入的参数控制剩余可用的左括号和右括号的数量，然后在递归体中进行判断，这样就不需要进行状态恢复。
class Solution {
public:
vector<string> res;
vector<string> generateParenthesis(int n) {
addParenthesis("", n, n);
return res;
}
void addParenthesis(string s, int left, int right) {
if (left == 0 && right == 0) { // 递归终止条件
res.push_back(s);
return;
}
if (left != 0) addParenthesis(s + "(", left - 1, right); // 通过传进来的参数判断是否需要进行递归，同时进入下一层时改变参数
if (right > left) addParenthesis(s + ")", left, right - 1);
}
};
但是在下面的Leetcode“组合”问题中，因为传入的参数 k 并没有在递归体中改变过，相应的终止条件也是假设 k 不变的，所以我们需要在递归（回溯）之后恢复状态。
class Solution {
public:
vector<vector<int>> combine(int n, int k) {
if (n <= 0 || k <= 0) return res;
vector<int> nums;
backtrack(nums, 1, n, k);
return res;
}
private:
vector<vector<int>> res;
void backtrack(vector<int> &nums, int start, int n, int k) {
// 递归终止条件
if (nums.size() == k) {
res.push_back(nums);
return;
}
// 进行回溯
for (int i = start; i <= n; ++i) {
nums.push_back(i); // 处理当前层逻辑
backtrack(nums, i + 1, n, k); // 递归，下探一层
nums.pop_back(); // 恢复状态
}
}
};
在本周的学习之前，我并未将回溯与递归在一起。但是经过覃超老师的讲解，我知道了其实回溯依赖于递归，或者说回溯是一种特殊的递归。其特殊之处就是每次递归开始前，我们先要改变传入参数的状态，而递归完之后则需要恢复参数的状态。这是高手学习的另一个特点，善于总结知识点之间的联系，形成知识框架。普通人学习只看到一个个孤立的知识点，而高手则能通过找到知识点的内在联系建立起知识体系。
了解了回溯的特点之后，解决起问题就容易多了，连以前视若猛虎的N皇后问题也能够比较轻松地理解并自己实现了。
这周算是在攻克回溯算法的路上踏出了第一步，但我知道想要真正攻克这些算法还有很长的路要有。接下来还要多思考、多练习，进一步加深自己对回溯（递归）算法的理解，提升自己解决相关问题的熟练度。
本周更重要的收获是了解了高手是如何学习的。他们不但善于总结解决问题的套路，能够做到举一反三。而且他们善于总结知识点之间的联系，形成知识框架。也许我们不是高手，自己无法总结出那些套路和知识体系，但我们可以向他们学习，将他们总结好的东西约过来！为此花点学费也是值得的。
