Knowledge Framework

Appearance

On this page

0. 学习结论 ​

  1. 树理论上都可以进行回溯算法，因为有路径，有选择列表。
  2. 遍历二叉树本质也是回溯算法，只是直接写了左右节点，替代选择列表循环。多叉树又回到了选择列表

1. 如何判断是回溯算法 ​

  1. 涉及穷举
  2. 可否构建决策树？
  3. 每个节点都有若干选择

决策树，与动态规划的树不同
【点没有意义，线为选择。】

动态规划的树：【状态在点上，线为选择】 本质上动态规划也是回溯算法，不过动态规划可以剪枝

2. 回溯算法步骤 ​

本质是解决一个决策树的遍历过程，也是穷举
概念：

  1. 路径：已做出的选择，路径的作用是为了某些返回可以推入结果，某些场景直接用树节点即可。
  2. 选择列表：当前可做的选择，二叉树直接写左右节点。
  3. 结束条件：到达决策树底层，无法再做选择的条件

步骤：

  1. 是否满足结束条件，满足则添加路径，返回
  2. for循环
    在递归前做选择，递归后撤销选择

目的是为了维护好【选择列表】和【路径】
路径和节点选择列表可以推算，不一定要数组，有时候可以节省大量时间

3. 回溯算法框架 ​

建立在多叉树的前序和后续操作上

js
var result = []
function backtrack(路径, 选择列表) {
   if (满足结束条件) {
      result.push(路径)
      return
   }

   for (选择 of 选择列表) {
      /* 过滤不合理选项 */
      if(不合理选项判断) continue

      /* 做选择 --START--*/
      将该选择从选择列表中移除  // 前序
      路径.push(选择)
      /* 做选择 --END--*/

      backtrack(路径, 选择列表)

      /* 撤销选择 --START--*/
      路径.pop(选择)// 后序
      将该选择恢复到选择列表中
      /* 撤销选择 --END-- */
   }
}

构建思路，树的前中后序列, 代表跟根的顺序

  1. 前序：根左右 进入某点之前执行的操作
  2. 中序：左根右 在某点时执行的操作
  3. 后序：左右根 离开某点之后执行的操作
js
// 前中后序
function traverse(root) {
   // 前序  进入某点之前执行的操作
   traverse(root.left)
   // 中序  在某点时执行的操作
   traverse(root.right)
   // 后序  离开某点之后执行的操作
}

// 多叉树
function traverse(root) {
   for (var child of root.children) {
      // 前序  进入某点之前执行的操作
      traverse(child)
      // 后序  离开某点之后执行的操作
   }
}

4. 细化问题点 ​

4.1 时间复杂度O(N!) ​

不像动态规划一样存在重叠子问题可以优化，回溯算法是纯暴力枚举，时间复杂度一般都很高。

4.2 本质是DFS 深度优先搜索 ​

总结 ​

课后疑问 ​

  1. 什么是状态，在股票题，状态代表的是dp[n - 1][K][0]中的n-1, k, 0/1。如何理解？

    • n-1, k, 0/1是状态，选择会改变的状态
    • dp是在多个状态共同作用下的值，这个值一般是所求值，也可以是过渡值

  2. 怎么定义出状态来，例如股票提3个状态https://labuladong.gitee.io/algo/3/26/96/

    • 一般把题目的变量列出来便是

参考资料 ​