回溯算法的刷题笔记，回溯专训
需积分: 5 201 浏览量
2022-04-03
17:27:26
上传
评论 3
收藏 4.54MB PDF 举报
所以 还有 很多人 将 回溯 问题的 本质 当作是 遍历一颗 决策树的 过程:
1.路径, 就是我们做出的决策(选择)
2.选择列表， 也就是 你当前 可以 做的 选择。
3. 结束条件 , 就是到达了 决策树的最底层了, 已然是 做完了 所有的决策了
请你看看这棵树: 好好理解一下 前序 其实是 当到达一颗结点的时候我们呢进行的操作 后序 其实是
我们离开每一颗 结点的 时候 进行的操作的:
回溯 : 在递归中 显现的 非常的明显 : 递归 ( 系统栈 ) 天然的 可以 实现
记录之前的信息 : 然后其实 可以利用递归的 系统栈 实现 我们 先到达 的递归树的最下面 一层
然后 开始回溯过程中 对于 每一层都进行一个操作： 这个 的 本质 就叫做 是 回
溯 算法的思想 : 回到之前 的 阶段: 其实 只要是 泛型的递归操作其中就一定是 包含了
回溯的 阶段的 递归函数的下面 其实 就是回溯操作了: 我们 到了 递归终点了 开始对于下面
的 回溯阶段的 东西做操作 然后 回溯算法 其实 会对于我们 修改的 东西 进行还原 : 撤
销 决策:
vector<> ans; //存储所有的可能结果的数组
void backtracking(路径, 选择列表){ //回溯框架
if (满足回溯终止条件) {
ans.push_back(当前的结果);
return ;
}
//说明了 没有到终止我们还需要继续向下做决策
for (选择: 本层集合元素 (树中结点孩子的数目就是集合的大小)) {
做决策;//路径.add(选择)
backtracking(路径, 选择列表);
撤销决策;//路径.remove(选择)
}
}
//学习数据结构的框架思维方式????? 是什么? 遍历一棵树 其实就是各种搜索问题的框架
//搜索树 其实 也就是这样子产生的...
请你自己看看这个东西:
void traverse(TreeNode* root) {
if (树的底层) {
return 结果;
}
//前序遍历的操作
traverse(child);
//后序遍历的操作 (所以其实 回溯 算是 二叉树的后序遍历的一种变型了)
}
剩余57页未读，继续阅读
评论0
最新资源