前置知识: 讲解003、讲解030、讲解031、讲解032、讲解033 - 位运算基础 讲解043 - 根据数据量猜解法的技巧，天字第一号重要技巧 讲解063 - 双向广搜 讲解067 - 从递归入手二维动态规划 【必备】课程的动态规划大专题从讲解066开始，建议从头开始学习会比较系统

本节课会讲述状压dp的原理以及4个题目，其中包括大名鼎鼎的TSP问题（题目4）

下节课会见识更多状压dp问题 & 更多技巧

注意： 轮廓线dp是状压dp中一类比较难的问题，【扩展】课程阶段讲述 插头dp是轮廓线dp中一类更难的问题，在笔试、面试中几乎没有出现的可能，不会安排。比赛同学自行学习

状压dp 设计一个整型可变参数status，利用status的位信息，来表示： 某个样本是否还能使用，然后利用这个信息进行尝试 写出尝试的递归函数 -> 记忆化搜索 -> 严格位置依赖的动态规划 -> 空间压缩等优化

如果有k个样本，那么表示这些样本的状态，数量是2^k 所以可变参数status的范围： 0 ~ (2^k)-1

样本每增加一个，状态的数量是指数级增长的，所以状压dp能解决的问题往往样本数据量都不大 一般样本数量在20个以内(10^6)，如果超过这个数量，计算量(指令条数)会超过 10^7 ~ 10^8 讲解043 - 根据数据量猜解法的技巧，天字第一号重要技巧

如果样本数量大到状压dp解决不了，或者任何动态规划都不可行，那么双向广搜是一个备选思路 讲解063 - 双向广搜

题目1 我能赢吗 给定两个整数n和m 两个玩家可以轮流从公共整数池中抽取从1到n的整数（不放回） 抽取的整数会累加起来（两个玩家都算） 谁在自己的回合让累加和 >= m，谁获胜 若先出手的玩家能稳赢则返回true，否则返回false 假设两位玩家游戏时都绝顶聪明，可以全盘为自己打算 测试链接 : https://leetcode.cn/problems/can-i-win/

注意：这道题有两个可变参数status、rest 但最关键的可变参数就1个，即status，表示还有哪些数字可以使用 另一个可变参数rest是被status决定的，所以只需要对status做缓存表 任何动态规划都是这样！只关注最关键的可变参数，被决定的可变参数不用管！不重要！

题目2 火柴拼正方形 你将得到一个整数数组 matchsticks 其中 matchsticks[i] 是第 i 个火柴棒的长度 你要用 所有的火柴棍 拼成一个正方形 你 不能折断 任何一根火柴棒，但你可以把它们连在一起，而且每根火柴棒必须 使用一次 如果你能拼出正方形，则返回 true ，否则返回 false 测试链接 : https://leetcode.cn/problems/matchsticks-to-square/

题目3 划分为k个相等的子集 给定一个整数数组nums和一个正整数k， 找出是否有可能把这个数组分成k个非空子集，其总和都相等 测试链接 : https://leetcode.cn/problems/partition-to-k-equal-sum-subsets/

状压dp vs 纯暴力的递归结合剪枝（不做任何动态规划）

状压dp：根据数据量进行复杂度的计算，发现可以通过，那就稳稳通过。推荐。因为能稳定通过。

纯暴力的递归（不做任何动态规划）：根据数据量进行复杂度的计算，发现不能通过，但是有大量剪枝的策略，有可能在数据状况并不严苛的情况下能通过，甚至时间还比状压dp快，这是有可能的。但是如果出题人刻意设置数据状况，那么一定无法通过。不推荐。因为不能稳定通过，并且方法本身没什么亮点。

题目4 售货员的难题 - TSP问题 某乡有n个村庄(1<=n<=20)，有一个售货员，他要到各个村庄去售货 各村庄之间的路程s(1<=s<=1000)是已知的 且A村到B村的路程，与B到A的路大多不同(有向带权图) 为了提高效率，他从商店出发到每个村庄一次，然后返回商店所在的村， 假设商店所在的村庄为1 他不知道选择什么样的路线才能使所走的路程最短 请你帮他选择一条最短的路 测试链接 : https://www.luogu.com.cn/problem/P1171

—— 本文来自火龙信奥（义乌睿码科技）：义乌青少年信息学奥赛与编程教育平台，专注 CSP-J/S、NOIP、GESP 竞赛培训，线上线下融合教学，助力编程升学。网址：hlcoding.com