算法：有穷 确定 可行 输入 输出

• 贪心
• 回溯
• 分治
• 减治
• 动态规划
  • 要素：阶段，状态，决策
  • 条件：最优子结构，无后效性
  • 适合：用空间换时间，适合有大量重复子问题的问题
• 递归
  • 消除递归：尾递归可用循环替代，单向递归可用迭代替代，其他可用显式栈替代

NPC 问题

适定性问题、三精确覆盖、子集和判定、集合划分、装箱问题、旅行商问题、哈密顿圈、顶点覆盖、背包问题、负有向圈最短路问题、整数规划

最大基数匹配是 P 问题，与最小覆盖问题弱对偶，与二分图强对偶。