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,等表示状态的
如果每个值都是不确定的,或者有多种可能,那么是没法进行状态压缩的。