线索

分析线索主要有如下四类：

• 递推
• 分类
• 有序
• 收敛

收敛

性质

1. 单调：严格单调递增或单调递减
2. 有界：有明确上界或者下界

逐级递减，可选状态空间逐级减少

出现位置

• 排列，每次能选的少一个

• 环图，设置单调收敛变量，保证每个节点只能被访问一次

  如 hashmap 的 visited

优化

有序

递推

只要DFS、BFS存在的地方都有递推

核心概念	简单解释
状态：状态定义	由实体状态和限制状态组成
边界：边界节点	边界节点 → 不依赖于任何状态点的已知点
递推：递推公式	不同节点的递推公式可以不同！！！
方向：拓扑排序	拓扑排序的方向确定

分类

树：分类结构，可以根据不同维度进行分类，并且类别不能重合

在动规的地方详细讲解