回溯算法入门
动态规划是能够通过子问题的求解推出总问题的答案。而回溯算法的解题思路比较简单,就是不断地做选择,当走不通的时候,就回溯到上一个节点,走别的路。解决一个回溯问题,实际上就是一个多叉树的遍历问题。
基本概念
1.路径:也就是已经做出的选择(已经走过的节点)。
2.选择列表:也就是你当前可以做的选择(当前节点面临的多个分支)。
3.结束条件:也就是到达决策树底层(叶子节点),无法再做选择的条件。
回溯算法的框架
1 | result = [] |
注:
- 做选择的就是将选择列表中的选择放入路径中,作为一个已经选择过的路径。
- 撤销选择的原因是当
for
循环遍历所有选择时,做完一个选择后,下一个选择还是基于上一个选择的,所以要恢复原来的(路径,选择列表),即回到上一个节点,本质其实就是DFS。
本博客所有文章除特别声明外,均采用 CC BY-NC-SA 4.0 许可协议。转载请注明来自 ae86's Blog!