30、算法与数据结构 - 实战：动态规划状态压缩技巧
can-i-win
力扣464题
https://leetcode.cn/problems/can-i-win/description/
在“100 game” 这个游戏中，两名玩家轮流选择从 1 到 10 的任意整数，累计整数和，先使得累计整数和 达到或超过 100 的玩家，即为胜者。
如果我们将游戏规则改为 “玩家 不能 重复使用整数” 呢？
例如，两个玩家可以轮流从公共整数池中抽取从 1 到 15 的整数（不放回），直到累计整数和 >= 100。
给定两个整数 maxChoosableInteger （整数池中可选择的最大数）和 desiredTotal（累计和），若先出手的玩家是否能稳赢则返回 true ，否则返回 false 。假设两位玩家游戏时都表现 最佳 。
暴力解
class Solution {
public boolean canIWin(int maxChoosableInteger, int desiredTotal) {
// 清洗无效参数
if (desiredTotal == 0) {
return true;
}
if ((maxChoosableInteger * (maxChoosableInteger + 1) >> 1) < desiredTotal) {
return false;
}
// 初始化一个状态数组，status[i]表示的时第i号数字有没有被拿走
// 拿走则为-1，没拿走就是i
int[] status = new int[maxChoosableInteger + 1];
for (int i = 1; i <= maxChoosableInteger; i++) {
status[i] = i;
}
return process(status, desiredTotal);
}
/**
* 当前还剩没拿的数记在status中，剩余rest要扣，当前的先手如果赢了，返回true，否则返回false
* @param status 当前还剩没拿的数记在status中
* @param rest 剩余rest要扣
* @return 先手返回true，后手返回false
*/
private boolean process(int[] status, int rest) {
// 当前先手面对0或者负数，先手输了
if (rest <= 0) return false;
for (int i = 0; i < status.length; i++) {
if (status[i] != -1) {
int num = status[i];
status[i] = -1;
// 接下来的先手，就是此时的后手，此时的后手输了，那么先手就赢了
if (!process(status, rest - num)) {
return true;
}
// 恢复现场
status[i] = num;
}
}
return false;
}
}
但是这个解是不通过，会超时
因此要优化为动态规划
但是可变参数有一个是数组类型，是不适宜改成动态规划的
因此看能否把该数组类型，改为整形
原型数组中的状态，用二进制位表示
中间解
暴力解把状态从数组改为整形的优化
class Solution {
public boolean canIWin(int maxChoosableInteger, int desiredTotal) {
// 清洗无效参数
if (desiredTotal == 0) {
return true;
}
if ((maxChoosableInteger * (maxChoosableInteger + 1) >> 1) < desiredTotal) {
return false;
}
// 现在不用状态数组了，改用一个整形，第i表示的时第i号数字有没有被拿走
// 拿走是1，没拿走是0
int status = 0;
return process(maxChoosableInteger, status, desiredTotal);
}
/**
* 当前还剩没拿的数记在status中，剩余rest要扣，当前的先手如果赢了，返回true，否则返回false
* @param choose 可以拿的数的范围 1~choose
* @param status 当前还剩没拿的数记在status中
* @param rest 剩余rest要扣
* @return 先手返回true，后手返回false
*/
private boolean process(int choose, int status, int rest) {
// 当前先手面对0或者负数，先手输了
if (rest <= 0) return false;
for (int i = 1; i <= choose; i++) {
if ((status & 1 << i) == 0) {
// 接下来的先手，就是此时的后手，此时的后手输了，那么先手就赢了
if (!process(choose, status | 1 << i, rest - i)) {
return true;
}
}
}
return false;
}
}
这样就等到了一个优化过后的中间解，
此时两个可变参数都是整形了，可以修改为动态规划
最终解
class Solution3 {
public boolean canIWin(int maxChoosableInteger, int desiredTotal) {
// 清洗无效参数
if (desiredTotal == 0) {
return true;
}
if ((maxChoosableInteger * (maxChoosableInteger + 1) >> 1) < desiredTotal) {
return false;
}
// 继续优化，那一个dp表，记录status对应的答案，如果下次递归遇到相同的status，直接拿值
// dp[status] status状态下，如果1表示先手赢，-1后手赢，0 没求过
int status = 0;
int[] dp = new int[1 << (maxChoosableInteger + 1)];
return process(maxChoosableInteger, status, desiredTotal, dp);
}
/**
* 当前还剩没拿的数记在status中，剩余rest要扣，当前的先手如果赢了，返回true，否则返回false
* @param choose 可以拿的数的范围 1~choose
* @param status 当前还剩没拿的数记在status中
* @param rest 剩余rest要扣
* @param dp 缓存表，dp[status] status状态对应的答案 != 0 表示以前已经求过了
* @return 先手返回true，后手返回false
*/
private boolean process(int choose, int status, int rest, int[] dp) {
if (dp[status] != 0) {
return dp[status] == 1;
}
// 当前先手面对0或者负数，先手输了
if (rest <= 0) {
dp[status] = -1;
return false;
}
for (int i = 1; i <= choose; i++) {
if ((status & 1 << i) == 0) {
// 接下来的先手，就是此时的后手，此时的后手输了，那么先手就赢了
if (!process(choose, status | 1 << i, rest - i, dp)) {
dp[status] = 1;
return true;
}
}
}
dp[status] = -1;
return false;
}
}
这种把存储状态信息的线性类型可变参数，压缩为整形参数的技巧，就是状态压缩
但是可以压缩的前提是，数组（或List）中的每一个值，都是0/1，true/false，等非黑即白的简单状态
TSP问题
有N个城市，任何两个城市之间的都有距离，任何一座城市到自己的
距离都是0。所有点到点的距离都存在一个N*N的二维数组matrix里，也就是
整张图有邻接矩阵表示。现要求一旅行商从k城市出发必须经过每一个城市且只在一个城市逗留一次，
最后回到出发的k城，返回总距离最短的路的距离。
暴力解
/**
* TPS问题
* 有N个城市，任何两个城市之间的都有距离，任何一座城市到自己的
* 距离都是0。所有点到点的距离都存在一个N*N的二维数组matrix里，也就是
* 整张图有邻接矩阵表示。现要求一旅行商从k城市出发必须经过每一个城市且只在一个城市逗留一次，
* 最后回到出发的k城，返回总距离最短的路的距离。
* 参数给定一个matrix，给定k。
*
* Created by huangjunyi on 2022/10/16.
*/
public class _01TSP {
/**
* TSP暴力解
* @param matrix
* @param k
* @return
*/
public static int tsp(int[][] matrix, int k) {
int N = matrix.length;
/*
用一个N长度的数组，里面的值0或1
记录还有哪些城市没到到
1代表还没到过，0代表到过
每到一个城市，从这个城市出发去往下一个城市之前
先把该城市在citys中的状态值修改为0
*/
int[] citys = new int[N];
for (int i = 0; i < citys.length; i++) {
citys[i] = 1;
}
/*
递归枚举每个可能路径，租后得出最短路径的长度
从k出发，最终回到k点
*/
return process(matrix, citys, k, k);
}
/**
* 递归每个出发点，最终回到老家
* @param matrix 城市距离表
* @param citys 还要去的城市
* @param start 当前出发点
* @param home 老家
* @return 走过的路的距离
*/
private static int process(int[][] matrix, int[] citys, int start, int home) {
// 计算还有多少城市要去
int cityNum = 0;
for (int i = 0; i < citys.length; i++) {
cityNum += citys[i] == 1 ? 1 : 0;
}
// 剩一座了，那就是当前这座城市，
// 因为在去往下一座城市时，才把当前城市标为已去过，
// 而现在刚到，还没有吧当前这座城市标记为已去过，
// 所以剩一座没去，那么就是现在这座，
// 那么剩下的路就是回老家了
if (cityNum == 1) {
return matrix[start][home];
}
// 枚举每个剩下没去的城市（除了老家以外），抓出最小答案
int min = Integer.MAX_VALUE;
citys[start] = 0;
for (int i = 0; i < citys.length; i++) {
if (citys[i] == 1) {
/*
matrix[start][i] + process(matrix, citys, i, home)
matrix[start][i] 从当前城市start，到下一座城市i，走的距离
process(matrix, citys, i, home) 从下一座城市i出发，走完剩下的距离，走过的距离
然后跟之前的最小值min PK一下
*/
min = Math.min(min, matrix[start][i] + process(matrix, citys, i, home));
}
}
// 深度遍历恢复现场
citys[start] = 1;
return min;
}
}
还是一样的套路，先把代表城市去没去过的citys数组，压缩为一个整形，用二进制位存储该城市起没去过
中间解
/**
* TPS问题
* 有N个城市，任何两个城市之间的都有距离，任何一座城市到自己的
* 距离都是0。所有点到点的距离都存在一个N*N的二维数组matrix里，也就是
* 整张图有邻接矩阵表示。现要求一旅行商从k城市出发必须经过每一个城市且只在一个城市逗留一次，
* 最后回到出发的k城，返回总距离最短的路的距离。
* 参数给定一个matrix，给定k。
*
* Created by huangjunyi on 2022/10/16.
*/
public class _02TSP {
/**
* TSP暴力解
* @param matrix
* @param k
* @return
*/
public static int tsp(int[][] matrix, int k) {
int N = matrix.length;
/*
在01中，使用一个N长度的数组记录城市状态信息如[0,1,1,0,1]
这里可以简化为用二进制位表示
citys有int数组类型简化为int类型
比如有5座城市，那么citys最开始应是11111
那么1左移5位得出100000，然后减一，就得11111
*/
int citys = (1 << N) - 1;
/*
递归枚举每个可能路径，租后得出最短路径的长度
从k出发，最终回到k点
*/
return process(matrix, citys, k, k);
}
/**
* 递归每个出发点，最终回到老家
* @param matrix 城市距离表
* @param citys 还要去的城市
* @param start 当前出发点
* @param home 老家
* @return 走过的路的距离
*/
private static int process(int[][] matrix, int citys, int start, int home) {
/*
一个数与上自身的取反加1，就得出二进制中最右侧1代表的值
这里如果条件成立，代表citys中只剩一座城市，就是start本身
那么就是直接从start回老家
*/
if (citys == (citys & (~citys + 1))) {
return matrix[start][home];
}
int min = Integer.MAX_VALUE;
// 把citys中start对应的状态位修改为0，表示start已经去过了，即将去往下一城市
citys &= (~(1 << start));
for (int i = 0; i < matrix.length; i++) {
if ((citys & (1 << i)) != 0) {
min = Math.min(min, matrix[start][i] + process(matrix, citys, i, home));
}
}
// 深度优先遍历恢复现场，把start状态位还原
citys |= (1 << start);
return min;
}
}
现在原先的citys数组压缩成了一个整形
可以在此基础上改成记忆化搜索的动态规划
最终解1
/**
* TPS问题
* 有N个城市，任何两个城市之间的都有距离，任何一座城市到自己的
* 距离都是0。所有点到点的距离都存在一个N*N的二维数组matrix里，也就是
* 整张图有邻接矩阵表示。现要求一旅行商从k城市出发必须经过每一个城市且只在一个城市逗留一次，
* 最后回到出发的k城，返回总距离最短的路的距离。
* 参数给定一个matrix，给定k。
*
* Created by huangjunyi on 2022/10/16.
*/
public class _03TSP {
/**
* TSP暴力解
* @param matrix
* @param k
* @return
*/
public static int tsp(int[][] matrix, int k) {
int N = matrix.length;
/*
在02中的基础上，添加记忆化搜索的优化
*/
int citys = (1 << N) - 1;
/*
一个记忆表
有 1 << N 行，代表这么多中状态
有 N 列，表示N个出发点
先初始化记忆表中所有的值为-1
*/
int[][] dp = new int[1 << N][N];
for (int i = 0; i < (i << N); i++) {
for (int j = 0; j < N; j++) {
dp[i][j] = -1;
}
}
/*
递归枚举每个可能路径，租后得出最短路径的长度
从k出发，最终回到k点
*/
return process(matrix, citys, k, k, dp);
}
/**
* 递归每个出发点，最终回到老家
* @param matrix 城市距离表
* @param citys 还要去的城市
* @param start 当前出发点
* @param home 老家
* @param dp
* @return 走过的路的距离
*/
private static int process(int[][] matrix, int citys, int start, int home, int[][] dp) {
// 记忆表中存在有效记录，直接返回
if (dp[citys][start] != -1) return dp[citys][start];
/*
一个数与上自身的取反加1，就得出二进制中最右侧1代表的值
这里如果条件成立，代表citys中只剩一座城市，就是start本身
那么就是直接从start回老家
*/
if (citys == (citys & (~citys + 1))) {
dp[citys][start] = matrix[start][home];
return dp[citys][start];
}
int min = Integer.MAX_VALUE;
// 把citys中start对应的状态位修改为0，表示start已经去过了，即将去往下一城市
citys &= (~(1 << start));
for (int i = 0; i < matrix.length; i++) {
if ((citys & (1 << i)) != 0) {
min = Math.min(min, matrix[start][i] + process(matrix, citys, i, home, dp));
}
}
// 深度优先遍历恢复现场，把start状态位还原
citys |= (1 << start);
dp[citys][start] = min;
return dp[citys][start];
}
}
最终解2
当然也可以改成标准的动态规划
/**
* TPS问题
* 有N个城市，任何两个城市之间的都有距离，任何一座城市到自己的
* 距离都是0。所有点到点的距离都存在一个N*N的二维数组matrix里，也就是
* 整张图有邻接矩阵表示。现要求一旅行商从k城市出发必须经过每一个城市且只在一个城市逗留一次，
* 最后回到出发的k城，返回总距离最短的路的距离。
* 参数给定一个matrix，给定k。
*
* Created by huangjunyi on 2022/10/16.
*/
public class _04TSP {
/**
* TSP暴力解
* @param matrix
* @param k
* @return
*/
public static int tsp(int[][] matrix, int k) {
int N = matrix.length;
/*
在02中的基础上，使用动态规划进行优化
*/
int home = k;
/*
一个dp表
有 1 << N 行，代表这么多中状态
有 N 列，表示N个出发点
*/
int[][] dp = new int[1 << N][N];
for (int citys = 0; citys < (1 << N); citys++) {
for (int start = 0; start < N; start++) {
// citys的start状态位为1，才有必要处理，否则这个格子是个无效的格子
if ((citys & (1 << start)) != 0) {
/*
一个数与上自身的取反加1，就得出二进制中最右侧1代表的值
这里如果条件成立，代表citys中只剩一座城市，就是start本身
那么就是直接从start回老家
*/
if (citys == (citys & (~citys + 1))) {
dp[citys][start] = matrix[start][home];
} else {
int min = Integer.MAX_VALUE;
// 把citys中start对应的状态位修改为0，表示start已经去过了，即将去往下一城市
int curCitys = citys & (~(1 << start));
for (int i = 0; i < matrix.length; i++) {
if ((curCitys & (1 << i)) != 0) {
min = Math.min(min, matrix[start][i] + dp[curCitys][i]);
}
}
dp[citys][start] = min;
}
}
}
}
return dp[(1 << N) - 1][0];
}
}
这种需要进行状态压缩的题是非常难的
而且可以进行状态压缩的前提是，线性结构里的每个值，都是简单的0/1，true/false，等表示状态的
如果每个值都是不确定的，或者有多种可能，那么是没法进行状态压缩的。