前置知识：讲解003、讲解030、讲解031、讲解032、讲解033 位运算基础、根据数据量猜解法、双向广搜、从递归入手二维动态规划

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

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

状压 dp

状压 dp（状态压缩）：设计一个整型可变参数 status，利用 status 的位信息，来表示：某个样本是否还能使用，然后利用这个信息进行尝试（相当于带了简单的路径信息）

写出尝试的递归函数
记忆化搜索
严格位置依赖的动态规划
空间压缩等优化

数据量说明

如果有 k 个样本，那么表示这些样本的状态，数量是 2^k

所以可变参数 status 的范围： 0 ~ (2^k)-1

样本每增加一个，状态的数量是指数级增长的，所以状压 dp 能解决的问题往往样本数据量都不大

一般样本数量在 20 个以内（ $1 0^{6}$ ），如果超过这个数量，计算量（指令条数）会超过 10^7 ~ 10^8：根据数据量猜解法的技巧-天字第一号重要技巧

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

备注

轮廓线 dp 是状压 dp 中一类比较难的问题，【扩展】课程阶段讲述

插头 dp 是轮廓线 dp 中一类更难的问题，在笔试、面试中几乎没有出现的可能，不会安排。比赛同学自行学习

题目1.我能赢吗

题目描述

在 “100 game” 这个游戏中，两名玩家轮流选择从 1 到 10 的任意整数，累计整数和，先使得累计整数和 达到或超过 100 的玩家，即为胜者。

如果我们将游戏规则改为 “玩家不能重复使用整数” 呢？

例如，两个玩家可以轮流从公共整数池中抽取从 1 到 15 的整数（不放回），直到累计整数和 >= 100。

给定两个整数 maxChoosableInteger （整数池中可选择的最大数）和 desiredTotal（累计和），若先出手的玩家能稳赢则返回 true ，否则返回 false 。假设两位玩家游戏时都表现最佳。

示例 1：

输入：maxChoosableInteger = 10, desiredTotal = 11

输出：false

解释：

无论第一个玩家选择哪个整数，他都会失败。

第一个玩家可以选择从 1 到 10 的整数。

如果第一个玩家选择 1，那么第二个玩家只能选择从 2 到 10 的整数。

第二个玩家可以通过选择整数 10（那么累积和为 11 >= desiredTotal），从而取得胜利.

同样地，第一个玩家选择任意其他整数，第二个玩家都会赢。

示例 2：

输入：maxChoosableInteger = 10, desiredTotal = 0

输出：true

示例 3：

输入：maxChoosableInteger = 10, desiredTotal = 1

输出：true

提示：

1 <= maxChoosableInteger <= 20
0 <= desiredTotal <= 300

测试链接

464.我能赢吗

答案

var (
	n     int
	m     int
	cache []*bool
)
 
func canIWin(maxChoosableInteger int, desiredTotal int) bool {
	n = maxChoosableInteger
	m = desiredTotal
	if m == 0 {
		// 来自题目规定
		return true
	}
	if (n*(n+1))>>1 < m {
		// 如果 1~n 数字全加起来
		// 累加和是 n * (n+1) / 2，都小于 m
		// 那么不会有赢家，也就意味着先手不会获胜
		return false
	}
	// 0000...（n 个 0）~1111...（n 个 1）
	cache = make([]*bool, 1<<(n+1))
	return f(1<<(n+1)-1, m)
}
 
// 如果 1~7 范围的数字都能选，那么 status 的状态为：
// 1 1 1 1 1 1 1 1
// 7 6 5 4 3 2 1 0
// 0 位弃而不用
// 如果 1~7 范围的数字，4、2 已经选了不能再选，那么 status 的状态为：
// 1 1 1 0 1 0 1 1
// 7 6 5 4 3 2 1 0
// 0 位弃而不用
// f 的含义：
// 数字范围 1~n，当前的先手，面对 status 给定的数字状态
// 在累加和还剩 rest 的情况下
// 返回当前的先手能不能赢（当前的先手可能是玩家 1 也可能是玩家 2）
func f(status, rest int) bool {
	if rest <= 0 {
		return false
	}
	if cache[status] != nil {
		return *cache[status]
	}
	ans := false
	for i := 1; i <= n; i++ {
		// 考察所有数字，但是不能选择之前选了的数字
		// 并且下一个玩家要输
		if status&(1<<i) != 0 && !f(status^(1<<i), rest-i) {
			ans = true
			break
		}
	}
	cache[status] = &ans
	return ans
}

复杂度

时间复杂度： $O (2^{n} * n)$
- $O (2^{n})$ ：dp 表大小
- $O (n)$ ：每个格子枚举代价
空间复杂度： $O (2^{n})$

备注

这道题有两个可变参数：status、rest

但最关键的可变参数就 1 个，即 status，表示还有哪些数字可以使用

另一个可变参数 rest 是被 status 决定的，所以只需要对 status 做缓存表

任何动态规划都是这样！只关注最关键的可变参数，被决定的可变参数不用管！不重要！

题目2.火柴拼正方形

题目描述

你将得到一个整数数组 matchsticks ，其中 matchsticks[i] 是第 i 个火柴棒的长度。你要用 所有的火柴棍 拼成一个正方形。你 不能折断 任何一根火柴棒，但你可以把它们连在一起，而且每根火柴棒必须 使用一次 。

如果你能使这个正方形，则返回 true ，否则返回 false 。

示例 1：

输入：matchsticks = [1,1,2,2,2]

输出：true

解释：能拼成一个边长为 2 的正方形。

示例 2：

输入：matchsticks = [3,3,3,3,4]

输出：false

解释：不能用所有火柴拼成一个正方形。

提示：

1 <= matchsticks.length <= 15
1 <= matchsticks[i] <= 10^8

测试链接

473.火柴拼正方形

答案

火柴拼正方形

var (
	nums  []int
	n     int
	limit int // 每条边的长度
	cache []*bool
)
 
func makesquare(matchsticks []int) bool {
	nums = matchsticks
	sum := 0
	for _, num := range nums {
		sum += num
	}
	// 剪枝：不能被 4 整除
	if sum%4 != 0 {
		return false
	}
	limit = sum / 4
	n = len(nums)
	cache = make([]*bool, 1<<n)
	return f(1<<n-1, 0, 4)
}
 
// status：哪些火柴没有用的位信息，1：没用；0：用了
// cur：当前要解决的这条边已经形成的长度
// rest：一共还有几条边没有解决
// 返回：能否用光所有火柴去解决剩下的所有边
// 因为调用子过程之前，一定保证每条边累加起来都不超过 limit
// 所以 status 是决定 cur 和 rest 的，关键可变参数只有 status
func f(status, cur, rest int) bool {
	// 火柴用完了，也没有剩下的边了
	if rest == 0 {
		return status == 0
	}
	if cache[status] != nil {
		return *cache[status]
	}
	ans := false
	for i := 0; i < n; i++ {
		// 考察每一根火柴，只能使用状态为 1 的火柴
		if status&(1<<i) != 0 && cur+nums[i] <= limit {
			if cur+nums[i] == limit {
				ans = f(status^(1<<i), 0, rest-1)
			} else {
				ans = f(status^(1<<i), cur+nums[i], rest)
			}
			if ans {
				break
			}
		}
	}
	cache[status] = &ans
	return ans
}

复杂度

时间复杂度： $O (2^{n} * n)$
- $O (2^{n})$ ：dp 表大小
- $O (n)$ ：每个格子枚举代价
空间复杂度： $O (2^{n})$

题目3.划分为 k 个相等的子集

题目描述

给定一个整数数组 nums 和一个正整数 k，找出是否有可能把这个数组分成 k 个非空子集，其总和都相等。

提示：

1 <= k <= len(nums) <= 16
0 < nums[i] < 10000
每个元素的频率在 [1,4] 范围内

测试链接

698.划分为k个相等的子集

状压 dp

状压 dp 的解法，这是最正式的解，时间复杂度： $O (2^{n} * n)$

划分为 k 个相等的子集

和题目2 几乎一样

var (
	theNums []int
	n       int
	limit   int
	cache   []*bool
)
 
func canPartitionKSubsets(nums []int, k int) bool {
	sum := 0
	for _, num := range nums {
		sum += num
	}
	if sum%k != 0 {
		return false
	}
	theNums = nums
	n = len(nums)
	limit = sum / k
	cache = make([]*bool, 1<<n)
	return f(1<<n-1, 0, k)
}
 
func f(status, cur, rest int) bool {
	if rest == 0 {
		return true
	}
	if cache[status] != nil {
		return *cache[status]
	}
	ans := false
	for i := 0; i < n; i++ {
		if status&(1<<i) != 0 && cur+theNums[i] <= limit {
			if cur+theNums[i] == limit {
				ans = f(status^(1<<i), 0, rest-1)
			} else {
				ans = f(status^(1<<i), cur+theNums[i], rest)
			}
			if ans {
				break
			}
		}
	}
	cache[status] = &ans
	return ans
}

暴力递归

纯暴力的递归（不做任何动态规划），利用良好的剪枝策略，可以做到非常好的效率

但这并不是正式的解，如果数据设计的很苛刻，是通过不了的

时间复杂度： $O (k^{n})$ ，一共有 n 个数，每个数有 k 种选择

var (
	theNums []int
	n       int
	limit   int
	group   []int
	K       int
)
 
func canPartitionKSubsets(nums []int, k int) bool {
	sum := 0
	for _, num := range nums {
		sum += num
	}
	// 剪枝：不能被 k 整除
	if sum%k != 0 {
		return false
	}
	sort.Ints(nums)
	n = len(nums)
	limit = sum / k
	// 剪枝：不能折断火柴
	if nums[n-1] > limit {
		return false
	}
	theNums = nums
	group = make([]int, k)
	K = k
	return f(n - 1)
}
 
// group 里面是各个集合已经有的累加和
// 随着递归的展开，group 里的累加和会变化
// 所以这是一个带路径的递归，而且路径信息比较复杂（group 数组）
// 无法改成动态规划，但是利用剪枝策略可以通过
// group[0:idx+1] 这些数字，填入每个集合，一定要都使用
// 每个集合的累加和一定都要是 limit，返回能不能做到
// idx：当前尝试的数字，数组已排序，先考虑大数字
func f(idx int) bool {
	if idx < 0 {
		return true
	}
	num := theNums[idx]
	// 遍历 group 的每个位置
	for i := 0; i < K; i++ {
		if group[i]+num <= limit {
			// 当前数字 num 放进 i 号集合
			group[i] += num
			if f(idx - 1) {
				return true
			}
			// 回溯：递归完成后将路径还原
			group[i] -= num
			// 剪枝：一个数在相同累加和的堆中都会尝试不过
			// 这里只做了连续的相同累加和堆的剪枝
			for i+1 < K && group[i] == group[i+1] {
				i++
			}
		}
	}
	return false
}

备注

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

题目4.售货员的难题（TSP 问题）

题目描述

某乡有 n 个村庄，有一个售货员，他要到各个村庄去售货

各村庄之间的路程 s 是已知的，且 A 村到 B 村的路程，与 B 到 A 的路大多不同（有向带权图）

为了提高效率，他从商店出发到每个村庄一次，然后返回商店所在的村，假设商店所在的村庄为 1

他不知道选择什么样的路线才能使所走的路程最短，请你帮他选择一条最短的路

数据规模：

1 <= n <= 20
1 <= s <= 1000

测试链接

P1171 售货员的难题

答案

package main
 
import (
	"bufio"
	"fmt"
	"math"
	"os"
	"strconv"
)
 
const (
	MAXN = 20
)
 
var (
	n     int
	graph = [MAXN][MAXN]int{} // 邻接矩阵建图，n 的数据量小，输入格式也是邻接矩阵
	cache = [1 << MAXN][MAXN]int{}
)
 
func main() {
	// s := `3
	// 0 2 1
	// 1 0 2
	// 2 1 0`
	// in := bufio.NewScanner(strings.NewReader(s))
	in := bufio.NewScanner(os.Stdin)
	in.Split(bufio.ScanWords)
	out := bufio.NewWriterSize(os.Stdout, 4096)
	for in.Scan() {
		n, _ = strconv.Atoi(in.Text())
		// 我们假设商店所在的村庄为 0
		// 数据就是：0~n-1
		for i := 0; i < n; i++ {
			for j := 0; j < n; j++ {
				in.Scan()
				graph[i][j], _ = strconv.Atoi(in.Text())
			}
		}
		build()
		fmt.Fprintln(out, compute())
	}
	out.Flush()
}
 
func build() {
	for s := 0; s < 1<<n; s++ {
		for i := 0; i < n; i++ {
			cache[s][i] = -1
		}
	}
}
 
func compute() int {
	// 商店所在的村庄为 0
	// 000001：0 位置走过了
	// 0：在 0 位置
	return f(1, 0)
}
 
// status：村里走没走过的状态，1：走过了不要再走了，0：没走过可以走
// idx：目前在哪个村
func f(status, idx int) int {
	if status == 1<<n-1 {
		// 村子都走过了，再走回 0 位置的商店即可
		return graph[idx][0]
	}
	if cache[status][idx] != -1 {
		return cache[status][idx]
	}
	ans := math.MaxInt
	for i := 1; i < n; i++ {
		// 1~n-1 这些村，都看看是不是下一个落脚点
		if status&(1<<i) == 0 {
			ans = min(ans, graph[idx][i]+f(status|(1<<i), i))
		}
	}
	cache[status][idx] = ans
	return ans
}

答案 2

正常来说上面的方法把 MAXN 改成 20 能通过，实现是正确的

问题是卡空间，而且 c++ 的实现不卡空间，java 和 go 的实现 Memory Limit Exceeded

需要绕一下，把起始点（商店）单独提出来，MAXN 降到 19，就可以通过了

package main
 
import (
	"bufio"
	"fmt"
	"math"
	"os"
	"strconv"
)
 
const (
	MAXN = 19
)
 
var (
	n     int
	start = [MAXN]int{} // start[i]：起始村到 i 号村的路程
	back  = [MAXN]int{} // back[i]：i 号村到起始村的路程
	graph = [MAXN][MAXN]int{} // 不包括起始村
	cache = [1 << MAXN][MAXN]int{} // 不包括起始村
)
 
func main() {
	in := bufio.NewScanner(os.Stdin)
	in.Split(bufio.ScanWords)
	out := bufio.NewWriterSize(os.Stdout, 4096)
	for in.Scan() {
		n, _ = strconv.Atoi(in.Text())
		// 除去起始村，起始村单独处理
		n--
		// 跳过起始村到起始村的路程
		in.Scan()
		// 读第一行
		for i := 0; i < n; i++ {
			in.Scan()
			start[i], _ = strconv.Atoi(in.Text())
		}
		for i := 0; i < n; i++ {
			// 读第一列
			in.Scan()
			back[i], _ = strconv.Atoi(in.Text())
			for j := 0; j < n; j++ {
				// 普通位置
				in.Scan()
				graph[i][j], _ = strconv.Atoi(in.Text())
			}
		}
		build()
		fmt.Fprintln(out, compute())
	}
	out.Flush()
}
 
func build() {
	for s := 0; s < 1<<n; s++ {
		for i := 0; i < n; i++ {
			cache[s][i] = -1
		}
	}
}
 
func compute() int {
	ans := math.MaxInt
	// 起始村无编号
	for i := 0; i < n; i++ {
		// 起始村到 i 号村 + i 号村出发所有村子都走最终回到起始村
		ans = min(ans, start[i]+f(1<<i, i))
	}
	return ans
}
 
// status：村里走没走过的状态，1：走过了不要再走了，0：没走过可以走
// idx：目前在哪个村
// status 不包含起始村
func f(status, idx int) int {
	if status == 1<<n-1 {
		// 村子都走过了，再走回 0 位置的商店即可
		return back[idx]
	}
	if cache[status][idx] != -1 {
		return cache[status][idx]
	}
	ans := math.MaxInt
	for i := 0; i < n; i++ {
		// 0~n-1 这些村，都看看是不是下一个落脚点
		if status&(1<<i) == 0 {
			ans = min(ans, graph[idx][i]+f(status|(1<<i), i))
		}
	}
	cache[status][idx] = ans
	return ans
}

复杂度

时间复杂度： $O (2^{n} * n^{2})$
- $O (2^{n} * n)$ ：二维 dp 表大小
- $O (n)$ ：每个格子枚举代价
空间复杂度： $O (2^{n} * n)$

备注

要求精确解，这个复杂度就是 TSP 问题的最优解了

但是可以用蚁群等其他算法求解其优良近似解

TSP 问题很有名，它甚至用来测试大型机、超型机的计算能力和算法的校验

My-Notes

全部文章

062.状压dp-上

状压 dp

数据量说明

备注

题目1.我能赢吗

题目描述

测试链接

答案

复杂度

备注

题目2.火柴拼正方形

题目描述

测试链接

答案

复杂度

题目3.划分为 k 个相等的子集

题目描述

测试链接

状压 dp

暴力递归

备注

题目4.售货员的难题（TSP 问题）

题目描述

测试链接

答案

答案 2

复杂度

备注

目录

反向链接

关系图谱