32
：学懂回溯法
source link: https://sexywp.com/learn-dp.htm
Go to the source link to view the article. You can view the picture content, updated content and better typesetting reading experience. If the link is broken, please click the button below to view the snapshot at that time.
回溯法，是算法面试和竞赛里面，最常使用的一种算法“套路”。实质上是一种“隐式图”的搜索算法，也有人说，就是一种类型的“深度优先搜索”（DFS），也是一种“递归”的典型应用，一种“枚举”法，也可以说是“暴力搜索”法。
我在 LeetCode 刷题的时候，遇到很多题目，被打上了“回溯法”的标签，然而还是不会做，真要写还是完全写不出来。于是，就下决心我一定要学会回溯法。至少，再看到类似的题目，不会感到畏惧。
要说回溯法的最经典题目，就是“八皇后”问题了，意思就是在国际象棋的棋盘上，放上八个皇后，这八个皇后，互相不能攻击，求出一种解法，或者求出所有解法，或者求出解的数量，都是这道题目的经典问法，也有扩展到“N皇后”问题。相信有所了解的读者一定不会陌生这题。（皇后，是国际象棋里，子力最强的一枚棋子，对横行，竖列，斜对角线，都会产生攻击）
这样的问题，我们是不能凭着自己的感觉，直接说出哪怕是一种答案的，更别提给出所有的答案。所以，需要使用算法来找出答案。最直观的想法，就是把皇后一个一个放到棋盘上，如果产生了攻击，就换一个位置放，直到所有 8 个皇后都摆放上去，就找到了一个正确的答案。
这样的 try and error 的方式，正是回溯法的思路。我想，这个思路如果静下心来，一点都不难理解，难点是怎么用代码把它写出来。如果掌握了这一点，所有类似的题目，就都可以解决了。
Recommend
About Joyk
Aggregate valuable and interesting links.
Joyk means Joy of geeK