约 8 分钟
当状态是“哪些元素已用/已选”且 n 很小(≤20),可把集合当下标做 DP,dp[S] 表示集合 S 的最优值。旅行商、覆盖类常用。核心是想清 S 的含义与转移(加入一个新元素)。
dp[S]
状压 DP 适用的典型数据范围是?
登录 后可看答案