动态规划

问题分类

P问题：多项式时间复杂度，$n^m$复杂度

N-P问题：非多项式复杂度，不可解

• $n!$，排列问题
• $2^n$，组合问题

动态规划：解决NP问题

把NP问题变成P问题

排列问题

• 排列，可能是连续性的
• 博弈，（需要换序）可能是非连续性的（但一定收敛）

组合问题

• 组合（无序）

  如：背包问题

• 选择（定序）

  如：LIS

• 分割（定序），本质上是对分割点的选择

  如：分割成几个符合条件的子数组之类的问题

串起来的线索：有序

本质上这五大类型就是建DAG图最主要的五种方式