核心思想
状压dp 设计一个整型可变参数status，利用status的位信息，来表示： 某个样本是否还能使用，然后利用这个信息进行尝试 写出尝试的递归函数 -> 记忆化搜索 -> 严格位置依赖的动态规划 -> 空间压缩等优化
如果有k个样本，那么表示这些样本的状态，数量是2^k 所以可变参数status的范围： 0 ~ (2^k)-1
样本每增加一个，状态的数量是指数级增长的，所以状压dp能解决的问题往往样本数据量都不大 一般样本数量在20个以内 (10^6)，如果超过这个数量，计算量 (指令条数) 会超过 10^7 ~ 10^8 讲解043 - 根据数据量猜解法的技巧，天字第一号重要技巧
如果样本数量大到状压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 <= 200 <= desiredTotal <= 300
注意：这道题有两个可变参数status、rest 但最关键的可变参数就1个，即status，表示还有哪些数字可以使用 另一个可变参数rest是被status决定的，所以只需要对status做缓存表 任何动态规划都是这样！只关注最关键的可变参数，被决定的可变参数不用管！不重要！
解题思路：
只能在数据量十分小的情况下
就是依靠位运算来表示每种可能的情况路径，每一位表示这个路径走过没。在本题表示为某个数字是否使用过，用0表示使用过了，后续递归调用不能再使用
暴力枚举每种路径情况
代码如下
package main.java.class080;
/**
* @program: ZuoChengxunAlgorithmClass
* @ClassName Code01_CanIWin
* @description: 我能赢吗
* // 给定两个整数n和m
* // 两个玩家可以轮流从公共整数池中抽取从1到n的整数（不放回）
* // 抽取的整数会累加起来（两个玩家都算）
* // 谁在自己的回合让累加和 >= m，谁获胜
* // 若先出手的玩家能稳赢则返回true，否则返回false
* // 假设两位玩家游戏时都绝顶聪明，可以全盘为自己打算
* // 测试链接 : https://leetcode.cn/problems/can-i-win/
* @author: zs宝
* @create: 2025-09-26 10:38
* @Version 1.0
**/public class Code01_CanIWin {
class Solution {
public boolean canIWin(int n, int m) {
if(m==0){
return true;
}
// 如果1~n数字全加起来
// 累加和和是n * (n+1) / 2，都小于m
// 那么不会有赢家，也就意味着先手不会获胜
if(n * (n + 1) / 2 < m){
return false;
}
//0：表示未使用过
//1：表示使用过且win
//-1：表示使用过且lose
int[]dp=new int[1 << (n+1)];
return f(n,(1<<(n+1))-1,m,dp);
}
// 如果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的情况下
// 返回当前的先手能不能赢，能赢返回true，不能赢返回false
//n:表示可以使用的数字的范围
//status:状态：表示还有那些数字可用，位运算。1表示可以用，0表示不可以用
//reset：还剩下的累积和
public boolean f(int n,int status,int reset,int[]dp){
if(reset<=0){
return false;
}
if(dp[status]!=0){
return dp[status]==1;
}
boolean ans=false;
for(int i=1;i<=n;i++){
// 考察所有数字，但是不能选择之前选了的数字
if((status & (1<<i))!=0 && !f(n,(status^(1<<i)),reset-i,dp)){
ans=true;
break;
}
}
dp[status]=ans?1:-1;
return ans;
}
}
}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 <= 151 <= matchsticks[i] <= 108
解题思路如下
这个题的数据量非常小，且我们需要每次枚举选择的那一根火柴
使用状压dp
这个题写代码时，犯了2个错误
首先是初始调用(1<<n)-1写的(1<<(n+1))-1, 状态数量估计错误
第二个是(status & (1<<i))!=0写成(status & (1<<i))== 1，但是位运算判断前面位置的状态，它的结果可能不是1，可能是2,4,8,16等等
利用位运算表示每一个数的使用情况，每次循环遍历每一根未使用火柴，但是要求当前边的长度+火柴长度<=边的长度，若等于，则边长度清0，下一次递归进入下一个边的判断，若不等，则长度+火柴长度，仍然下次递归考虑当前边
代码如下
package main.java.class080;
/**
* @program: ZuoChengxunAlgorithmClass
* @ClassName Code02_MatchsticksToSquare
* @description: 火柴拼正方形
* // 你将得到一个整数数组 matchsticks
* // 其中 matchsticks[i] 是第 i 个火柴棒的长度
* // 你要用 所有的火柴棍 拼成一个正方形
* // 你 不能折断 任何一根火柴棒，但你可以把它们连在一起，而且每根火柴棒必须 使用一次
* // 如果你能拼出正方形，则返回 true ，否则返回 false
* // 测试链接 : https://leetcode.cn/problems/matchsticks-to-square/
* @author: zs宝
* @create: 2025-09-27 09:55
* @Version 1.0
**/public class Code02_MatchsticksToSquare {
class Solution {
public boolean makesquare(int[] matchsticks) {
int n=matchsticks.length;
int sum=0;
for(int num:matchsticks){
sum+=num;
}
if(sum%4!=0){
return false;
}
int limit=sum/4;
int[]dp=new int[1<<n];
return f(matchsticks,n,limit,(1<<n)-1,0,4,dp);
}
/**
limit:限定的当前边的长度
status:位运算表示那些火柴使用过了
cur:当前边的长度
reset:还差多少条边
*/
public boolean f(int[] matchsticks,int n,int limit,int status,int cur,int reset,int[]dp){
if(reset==0){
return status==0;
}
if(dp[status]!=0){
return dp[status]==1;
}
boolean ans=false;
//状压dp，开始选边
for(int i=0;i<n;i++){
if((status & (1<<i))!=0 && cur+matchsticks[i]<=limit){
if(cur+matchsticks[i]==limit){
ans=f(matchsticks,n,limit,status^(1<<i),0,reset-1,dp);
}else{
ans=f(matchsticks,n,limit,status^(1<<i),cur+matchsticks[i],reset,dp);
}
if(ans){
break;
}
}
}
dp[status]=ans?1:-1;
return ans;
}
}
}3、划分为k个相等的子集
题目如下： 给定一个整数数组 nums 和一个正整数 k，找出是否有可能把这个数组分成 k 个非空子集，其总和都相等。
示例 1：
输入： nums = [4, 3, 2, 3, 5, 2, 1], k = 4 输出： True 说明： 有可能将其分成 4 个子集（5），（1,4），（2,3），（2,3）等于总和。
示例 2:
输入: nums = [1,2,3,4], k = 3 输出: false
提示：
1 <= k <= len(nums) <= 160 < nums[i] < 10000每个元素的频率在
[1,4]范围内
解题思路：
这个题与第二个题几乎一致的状压dp思路
但是这个题可以用暴力递归+剪枝通过
状压dp vs 纯暴力的递归结合剪枝（不做任何动态规划）
状压dp：根据数据量进行复杂度的计算，发现可以通过，那就稳稳通过。推荐。因为能稳定通过。
纯暴力的递归（不做任何动态规划）：根据数据量进行复杂度的计算，发现不能通过，但是有大量剪枝的策略，有可能在数据状况并不严苛的情况下能通过，甚至时间还比状压dp快，这是有可能的。但是如果出题人刻意设置数据状况，那么一定无法通过。不推荐。因为不能稳定通过，并且方法本身没什么亮点。
代码如下
package main.java.class080;
import java.util.Arrays;
/**
* @program: ZuoChengxunAlgorithmClass
* @ClassName Code03_PartitionToKEqualSumSubsets
* @description: 划分为k个相等的子集
* // 给定一个整数数组 nums 和一个正整数 k，
* // 找出是否有可能把这个数组分成 k 个非空子集，其总和都相等。
* // 测试链接 : https://leetcode.cn/problems/partition-to-k-equal-sum-subsets/
* @author: zs宝
* @create: 2025-09-27 10:41
* @Version 1.0
**/public class Code03_PartitionToKEqualSumSubsets {
class Solution {
//状压dp解法
public boolean canPartitionKSubsets1(int[] nums, int k) {
int n = nums.length;
int sum = 0;
for (int num : nums) {
sum += num;
}
if (sum % k != 0) {
return false;
}
int limit = sum / k;
int[] dp = new int[1 << n];
return f1(nums, n, limit, (1 << n) - 1, 0, k, dp);
}
/**
* limit:限定的当前边的长度
* status:位运算表示那些火柴使用过了
* cur:当前边的长度
* reset:还差多少条边
*/
public boolean f1(int[] nums, int n, int limit, int status, int cur, int reset, int[] dp) {
if (reset == 0) {
return status == 0;
}
if (dp[status] != 0) {
return dp[status] == 1;
}
boolean ans = false;
//状压dp，开始选边
for (int i = 0; i < n; i++) {
if ((status & (1 << i)) != 0 && cur + nums[i] <= limit) {
if (cur + nums[i] == limit) {
ans = f1(nums, n, limit, status ^ (1 << i), 0, reset - 1, dp);
} else {
ans = f1(nums, n, limit, status ^ (1 << i), cur + nums[i], reset, dp);
}
if (ans) {
break;
}
}
}
dp[status] = ans ? 1 : -1;
return ans;
}
//暴力递归的解法+剪枝优化
public boolean canPartitionKSubsets2(int[] nums, int k) {
int n = nums.length;
int sum = 0;
for (int num : nums) {
sum += num;
}
if (sum % k != 0) {
return false;
}
int target = sum / k;
Arrays.sort(nums);
return f2(nums, new int[k], n - 1, target);
}
//将nums数组分为K份，要求每份累加和相等
//group数组存储每份的累加和
public boolean f2(int[] nums, int[] group, int index, int target) {
if (index < 0) {
return true;
}
int len = group.length;
int num = nums[index];
for (int i = 0; i < len; i++) {
if (group[i] + num <= target) {
group[i] += num;
if (f2(nums, group, index - 1, target)) {
return true;
}
//复原
group[i] -= num;
while (i + 1 < len && group[i] == group[i + 1]) {
i++;
}
}
}
return false;
}
}
}4、售货员的难题 - TSP问题
题目描述
某乡有 n 个村庄，有一个售货员，他要到各个村庄去售货，各村庄之间的路程 s_{i,j} 是已知的，且 A 村到 B 村与 B 村到 A 村的路大多不同。为了提高效率，他从商店出发到每个村庄一次，然后返回商店所在的村，假设商店所在的村庄为 1，他不知道选择什么样的路线才能使所走的路程最短。请你帮他选择一条最短的路。
输入格式
第一行是一个整数，表示村庄数 n。 接下来 n 行，每行 n 个整数，第 i 行的第 j 个整数表示 i 到 j 的单向路径的距离 s_{i,j}。 输出格式
一行一个整数表示最短的路程。 输入输出样例 #1 输入 #1
3
0 2 1
1 0 2
2 1 0输出 #1
3说明/提示
对全部的测试数据，保证 2 \leq n \leq 20，1 \leq s_{i,j} < 10^3。
解题思路：
这道题是图论中大名鼎鼎的旅行商问题
由于数据量较小，因此可以用状压dp来做
但是本题我写的是时候，老是将第一次调用的递归的当前状态写错。
这个题在洛谷上，按照标准的状压dp写法，最后一个测试数据会空间超过爆红，但是同样的写法思路C++可过，Java不能过
因此有第二种写法，另辟蹊径，将源点的相关路径提取到另外两个数组start，back中去。但是其实两种写法的思路是一样的
代码如下： 标准状压dp写法
package main.java.class080;
import java.io.*;
import java.util.Arrays;
/**
* @program: ZuoChengxunAlgorithmClass
* @ClassName Code04_TSP1
* @description: 售货员的难题 - TSP问题
* // 某乡有n个村庄(1<=n<=20)，有一个售货员，他要到各个村庄去售货
* // 各村庄之间的路程s(1<=s<=1000)是已知的
* // 且A村到B村的路程，与B到A的路大多不同(有向带权图)
* // 为了提高效率，他从商店出发到每个村庄一次，然后返回商店所在的村，
* // 假设商店所在的村庄为1
* // 他不知道选择什么样的路线才能使所走的路程最短
* // 请你帮他选择一条最短的路
* // 测试链接 : https://www.luogu.com.cn/problem/P1171
* @author: zs宝
* @create: 2025-09-27 11:12
* @Version 1.0
**/// 正常来说把MAXN改成20能通过，实现是正确的
// 问题是卡空间，而且c++的实现不卡空间，就卡java的实现
// 但如果把MAXN改成19，会有一个测试用例通过不了
// 那就差这么一点空间...看不起java是吗？
// 好，你歧视java实现，那就别怪我了
// 完全能通过的版本看Code04_TSP2的实现
public class Code04_TSP1 {
public static int MAXN=20;
public static int[][]graph=new int[MAXN][MAXN];
public static int[][]dp=new int[1<<MAXN][MAXN];
public static int n;
public static void build(){
for(int i=0;i<1<<n;i++){
for(int j=0;j<n;j++){
dp[i][j]=-1;
}
}
}
public static void main(String[] args) throws IOException {
BufferedReader buffer=new BufferedReader(new InputStreamReader(System.in));
StreamTokenizer in=new StreamTokenizer(buffer);
PrintWriter out=new PrintWriter(new OutputStreamWriter(System.out));
while (in.nextToken()!=StreamTokenizer.TT_EOF){
n=(int)in.nval;
build();
for(int i=0;i<n;i++){
for(int j=0;j<n;j++){
in.nextToken();
graph[i][j]=(int)in.nval;
}
}
out.println(compute());
}
out.flush();
out.close();
buffer.close();
}
public static int compute(){
//初始状态由于售货员在第一个村庄，因此初始状态第一个村庄置为1
//1：表示走过村庄
//0:表示未走过村庄
return f(0,1);
}
/**
* * @param cur 当前村庄
* @param status 当前位运算表示状态，那些村庄已经走过了
* @return
*/
public static int f(int cur,int status){
if(status==(1<<n)-1){
return graph[cur][0];
}
if(dp[status][cur]!=-1){
return dp[status][cur];
}
int ans=Integer.MAX_VALUE;
//开始遍历寻找最小值
for(int i=0;i<n;i++){
//只能走未走过的村庄
if((status & (1<<i))==0){
ans=Math.min(ans,graph[cur][i]+f(i,status| (1<<i)));
}
}
dp[status][cur]=ans;
return ans;
}
}这个题专门为Java而过的改动写法
package main.java.class080;
import java.io.*;
/**
* @program: ZuoChengxunAlgorithmClass
* @ClassName Code04_TSP2
* @description: 售货员的难题 - TSP问题
* // 某乡有n个村庄(1<=n<=20)，有一个售货员，他要到各个村庄去售货
* // 各村庄之间的路程s(1<=s<=1000)是已知的
* // 且A村到B村的路程，与B到A的路大多不同(有向带权图)
* // 为了提高效率，他从商店出发到每个村庄一次，然后返回商店所在的村，
* // 假设商店所在的村庄为1
* // 他不知道选择什么样的路线才能使所走的路程最短
* // 请你帮他选择一条最短的路
* // 测试链接 : https://www.luogu.com.cn/problem/P1171
* @author: zs宝
* @create: 2025-09-27 11:53
* @Version 1.0
**/public class Code04_TSP2 {
public static int MAXN=19;
public static int[][]graph=new int[MAXN][MAXN];
public static int[][]dp=new int[1<<MAXN][MAXN];
public static int n;
//记录第0行位置的元素，即售货点与各个村庄的位置
public static int[] start = new int[MAXN];
//记录各个村庄到售货点的位置
public static int[] back = new int[MAXN];
public static void build(){
for(int i=0;i<1<<n;i++){
for(int j=0;j<n;j++){
dp[i][j]=-1;
}
}
}
public static void main(String[] args) throws IOException {
BufferedReader buffer=new BufferedReader(new InputStreamReader(System.in));
StreamTokenizer in=new StreamTokenizer(buffer);
PrintWriter out=new PrintWriter(new OutputStreamWriter(System.out));
while (in.nextToken()!=StreamTokenizer.TT_EOF){
//现在我们将售货点村庄单独排在外面，有关售货点与村庄的距离关系全部放在start和back数组中
n=(int)in.nval-1;
build();
in.nextToken();
//记录售货点村庄到其它村庄的距离
for(int i=0;i<n;i++){
in.nextToken();
start[i]=(int)in.nval;
}
for(int i=0;i<n;i++){
in.nextToken();
back[i]=(int)in.nval;
for(int j=0;j<n;j++){
in.nextToken();
graph[i][j]=(int)in.nval;
}
}
out.println(compute());
}
out.flush();
out.close();
buffer.close();
}
public static int compute(){
int ans=Integer.MAX_VALUE;
for(int i=0;i<n;i++){
ans=Math.min(ans,start[i]+f(1<<i,i));
}
return ans;
}
public static int f(int status,int cur){
if(status==(1<<n)-1){
return back[cur];
}
if(dp[status][cur]!=-1){
return dp[status][cur];
}
int ans=Integer.MAX_VALUE;
for(int i=0;i<n;i++){
if((status & (1<<i))==0){
ans=Math.min(ans,f(status | (1<<i),i)+graph[cur][i]);
}
}
dp[status][cur]=ans;
return ans;
}
}