力扣LeetCode 837题：新 21 点（超详解排列组合的坑，我可以，你也可以）

蔚落 2023-02-15 07:56 45阅读 0赞

题目：

> 爱丽丝参与一个大致基于纸牌游戏 “21点” 规则的游戏，描述如下：  
>   
> 爱丽丝以 0 分开始，并在她的得分少于 K 分时抽取数字。 抽取时，她从 \[1, W\] 的范围中随机获得一个整数作为分数进行累计，其中 W 是整数。 每次抽取都是独立的，其结果具有相同的概率。  
>   
> 当爱丽丝获得不少于 K 分时，她就停止抽取数字。 爱丽丝的分数不超过 N 的概率是多少？

示例 1：
    输入：N = 10, K = 1, W = 10
    输出：1.00000
    说明：爱丽丝得到一张卡，然后停止。
    
    示例 2：
    输入：N = 6, K = 1, W = 10
    输出：0.60000
    说明：爱丽丝得到一张卡，然后停止。
    在 W = 10 的 6 种可能下，她的得分不超过 N = 6 分。
    
    示例 3：
    输入：N = 21, K = 17, W = 10
    输出：0.73278
    
    提示：
    0 <= K <= N <= 10000
    1 <= W <= 10000
    如果答案与正确答案的误差不超过 10^-5，则该答案将被视为正确答案通过。
    此问题的判断限制时间已经减少。

### 一、题目分析： ###

我们换个方式表述一下或许会更清楚，因为他确实是类似于 **21 点** 这样的纸牌游戏。

我们想一想 **纸牌游戏**，和这个题目对应：

1.  抽牌的范围是固定的，1-13，对应到题目里就是 **W=13**；
2.  **K=21**。拿牌的时候，可能拿了好几张，总数都不到 21，再多拿一张，就>=21了，那么游戏结束。可以想到，游戏总会结束；
3.  当 >=21 的那一刹那，也就是游戏结束的时候，手里的牌值，可能超过 **N** 了，也可能没有超过 N。

从第三步看的出来，**得分不超过 N** 这件事，有一个概率，我们要求的就是这个概率。

### 二、方法 1 ：递归排列组合 ###

模拟抽牌的游戏，每一次拿牌都可能拿到任意一张，接着继续，继续，那么每次游戏结束的时候，拿牌的组合数是有限的，其中有多少是 不超过 N 的，做除法，就是概率。

> 示例 1 里面， 从 \[1,10\] 随便拿一张牌就会 >=k ，所以拿牌这件事，总共的组合数有 10 种。这些组合里每一个都 <=10，也就是不超过 N 的组合数有10个。 那么满足条件的概率就是 10/10=1.00000。  
>   
> 示例 2 里面，从 \[1,10\] 随便拿一张牌就会 >= k，所以拿牌这件事，总共的组合数有 10 种。这些组合里 \[1,2,3,4,5,6\] 是 <=6 的，\[7,8,9,10\] 是超过了 N 的。 那么满足条件的概率就是 6/10=0.60000。  
>   
> 示例 3 里面，从 \[1,10\] 拿几张牌，到达>=17的临界点的组合数有很多种，其中<=21的有很多种，这个算起来比较麻烦。**这里就不算了**。

我们直接按照思路写成代码：

class Solution {
        
    
        private double total=0;
        private double below=0.0;
        public double new21Game(int N, int K, int W) {
        
            
            count(0 , N, K, W);
            return below/total;//返回满足不超过 N 的组合数/总组合数
        }
    
        //抽牌的递归算法
        public void count(int temp , int N , int K , int W){
        
            //判断是否结束，即已经超过K
            if(temp>=K){
        
                total++;
                //如果在结束的同时满足不超过 N 的条件
                if(temp<=N){
        
                    below++;
                }
                return;
            }else{
        
                //否则继续抽牌
                for(int i=1 ; i<=W ; i++){
        
                    count(temp+i , N , K , W);
                }
            }
        }
    }

答案错误。

###### 发现问题了么？ ######

这么算**排列组合**是不行的！！！按照我们本来的算法，正好在可能出问题的示例3，我们偷懒了。。。

再回过头来分析一下：

##### 每一种组合，作为一个事件，都有自身出现的概率。 #####

假设，N 是 11 ，K 是 7，W 是 10。

比如下面两种组合：

1.“第一张牌，我拿到的是8，就大于K，结束”
    2.“第一张牌，我拿到了2，那么游戏继续，此时又在[1,w]之间选了一张牌是7，然后发现大于8了，结束。”

这两件事，如果按照我们的方法，是分母里的两种情况，只用 count+2 就可以完成。

但是这两件事本身来说，他发生的概率是不一样的：

##### 第一件事发生的概率就是1/10，而第二件事发生的概率是(1/10) \* (1/10)。 #####

所以这两种 组合 不能 **“平等”** 的被算进去，而是要加权重的。。。

加了权重的方式，我们在每多递归一层，显然要乘上多一次出现的概率，也就是 **1/W**。

在此基础上修改代码：

class Solution {
        
        private double total=0;
        private double below=0.0;
        public double new21Game(int N, int K, int W) {
        
            count(0 , 0, N, K, W);//调用模拟算法
    
            return below/total;//返回满足不超过 N 的组合数/总组合数
        }
    
        //抽牌的递归算法
        public void count(int temp ,double layer, int N , int K , int W){
        
            //判断是否结束，即已经超过K
            if(temp>=K){
        
                total+=1/Math.pow(W, layer);
                //如果在结束的同时满足不超过 N 的条件
                if(temp<=N){
        
                    below+=1/Math.pow(W,layer);
                }
                return;
            }else{
        
                //否则继续抽牌
                for(int i=1 ; i<=W ; i++){
        
                    count(temp+i ,layer+1, N , K , W);
                }
            }
        }
    }

然后，超时了，很显然，因为从一开始的 1~W 分支，再分别进行递归（最坏情况又是 1~W 分支……），时间复杂度是指数级别的。

上面的递归代码可以进行修改，由于分母的总数也是乘了概率，总和一定是 1 ，所以可以直接省略，改为用一个 p 来计算分子的值。（这种写法有助于理解下面的动态规划）

class Solution {
        
        private double p=0;
        public double new21Game(int N, int K, int W) {
        
            count(0 , 0, N, K, W);
            return p;
        }
    
        //抽牌的递归算法
        public void count(int temp ,double layer, int N , int K , int W){
        
            if(temp>=K){
        
                if(temp<=N){
        
                    p+=1/Math.pow(W,layer);
                }
                return;
            }else{
        
                for(int i=1 ; i<=W ; i++){
        
                    count(temp+i ,layer+1, N , K , W);
                }
            }
        }
    }

### 三、方法 2 ：动态规划 ###

一般情况来说，递归是把问题一步一步划分成子问题的 “分治”，然后再回来求解。

而动态规划的思路也是基于这种“分治”思想，不过在此基础上进行了优化，所以可以用动态规划来代替递归。

参考下面这篇博客对于动态规划和递归联系，区别的讲解：

[动态规划和递归的联系][Link 1]

回过头来。  
这道题目能想到递归的方法，只是超时，因此动态规划应该也可以做出来。  
为了方便找到最优子结构和状态转移式，现在我们先来思考递归方法里的这个计算过程：

if(temp>=K){
        
                if(temp<=N){
        
                    p+=1/Math.pow(W,layer);
                }
                return;
            }

这个式子代表的是，对于 **某一种拿牌的组合** 前一步在继续递归，而这一步获胜了，停止了递归。

我们想象这个计算式如果展开写，应该是

> **(1/W)1 \+ (1/W)2 \+ … … + (1/W)layer**

过程里的次数 1 ~ layer 一定是连续的，因为只要你在继续拿牌，那么拿到某一张牌的概率都是一定的，就要在原来的概率基础上 乘以 1/W 。  
其中的 layer 虽然不知道，但我们知道 layer 的范围，**大于等于1，小于等于K**。

因此，到这里我们也能反应过来，在计算过程中，肯定存在多个一样的 layer ，对应的概率中间值我们在递归里重复计算了。**动态规划就是来解决这个重复的问题的，因为动态规划会保存过程里的解，需要时直接拿来计算。**

按照动态规划的思路，我们来思考：

某一个中间时刻，当我拿牌得分已经拿到了 i 分，接着我从 \[1,W\] 里任选一个，游戏获胜的概率是多少？记为 **dp\[i\]**

答案：选择任意一个的概率是 1/W ，在选择了之后，我们还需要知道选择了任意一个的 **下一个时刻** 获胜的概率分别是多少。

> 如果按照递归，我们要继续算下去，就是新的套娃过程了，但这里我们仍然记作未知数

显然，这些 **下一个时刻的概率** 分别就是 拿到了 i+1 , i+2 ,… , i+W 分数时获胜的概率，也就是**dp\[i+1\] ,dp\[i+2\], … … ,dp\[i+W\]**

这些概率里，有的会继续计算多层的 (1/W) layer，有的就直接结束，我们先不去考虑。但是不是有了一点状态转移方程的意思？

用dp\[i\] 表示 当前已经得到了 i 分时，能赢得游戏的概率。

那么

> **dp\[i\] = (1/W) \* ( dp\[i+1\] + dp\[i+2\] + … + dp\[i+W\] )**

这就是我们的状态转移方程。

到这里可以发现，我们最终要求的结果，是 dp\[0\] ，也就是从没有拿牌开始计算.

如果计算的过程采用一步一步套下去，和递归没有任何差别，并且，在递归计算每一个 dp\[i\] 的时候，式子里存在了在其他递归里的重复计算。

因此我们选择逆向计算。具体实现过程：

**预处理：** dp\[\] 后半段先进行初始化。  
既然 i 最大是 K-1， 那么对应拿到的牌最大就是 K-1+W。对于每一个 i ，计算的时候需要用到 dp\[i+W\] 。而这些 i > K 的范围里，代表任意拿一张牌得分即超过K，游戏结束，如果得到的分数 <=N ，那么赢得游戏的概率是1，否则是0，所以要在这些位置预先填入 1 和 0。看代码更直接：

for (int i=K; i<=N && i<K+W; i++) {
        
                dp[i] = 1.0;
            }

中间过程：

*  循环计算 i 的范围：\[0,1,…,K-1\]（因为 i 是K 的时候游戏结束，就不能抽牌了)
 *  既然选择逆向，初始 i = K-1
 *  中间状态转移，dp\[i\] =( 1/W ) \* sum( dp\[i+1\],dp\[i+2\],…dp\[i+W\] )
 *  结束：return dp\[0\]

对应这个思路可以写出第一版代码：

class Solution {
        
        public double new21Game(int N, int K, int W) {
        
            if (K == 0) {
        
                return 1.0;
            }
    
            double[] dp = new double[K + W];//对应最大的i是K-1+W
    
            //后半段概率为1的提前填入。
            for (int i=K; i<=N && i<K+W; i++) {
        
                dp[i] = 1.0;
            }
    
            //逆序dp
            for (int i=K-1; i>=0; i--) {
        
                //进行状态转移的sum过程
                for (int j = 1; j <= W; j++) {
        
                    dp[i] += dp[i+j] / W;
                }
            }
            return dp[0];
        }
    }

这个代码的时间复杂度应该是O(N+KW)，提交仍然超时（可见我们第一种模拟的排列组合法超的应该更厉害）。

需要优化。  
肉眼可见，时间复杂的点在于，sum的过程需要循环求和，然鹅我们知道这个过程的移动：

**dp\[ i \]　= (1/W) \* (dp\[i+1\] + dp\[i+2\] + … + dp\[i+W-1\] \+ dp\[i+W\])；  
dp\[i-1\] = (1/W) \* (dp\[i-1+1\] + dp\[i-1+2\] + … + dp\[i-1+W-1\] + dp\[i-1+W\])　　　　  
　　　= (1/W) \* (dp\[i\] \+ dp\[i+1\] + dp\[i+2\] + … + dp\[i+W-1\] )**

区别只是**少了一个最后项，最前面多了一个项**而已。**很清楚吧？**

如果我们每次都for循环来计算加和，那时间复杂度是O(n)，但是如果我们只计算加一项减一项，那时间复杂度是O(1)，具体实现也是很常用的操作，叫做“滑动窗口”，让这个窗口跟着我们 i-- 的时候向前挪动就可以，也就是进行加一项减一项的操作。

来看最终代码：

class Solution {
        
        public double new21Game(int N, int K, int W) {
        
            if (K == 0) {
        
                return 1.0;
            }
    
            double[] dp = new double[K + W];//对应最大的i是K-1+W
    
            //后半段概率为1的提前填入。
            for (int i=K; i<=N && i<K+W; i++) {
        
                dp[i] = 1.0;
            }
    
            //计算从 K 到 W 位置的这一段长度为 W 的窗口长度
            for (int j=K; j<=N && j<=K+W; j++){
        
                dp[K-1] += dp[j];
            }
            dp[K-1]/=W;
            //逆序dp
            for (int i=K-2; i>=0; i--) {
        
                //进行状态转移，利用滑动窗口
                dp[i] = dp[i+1] - (dp[i+1+W])/W + (dp[i+1])/W;
            }
            return dp[0];
        }
    }

其中，计算窗口长度也可以这样：

//计算从 K 到 W 位置的这一段长度为 W 的窗口长度，代替循环
       dp[K - 1] = 1.0 * Math.min(N - K + 1, W) / W;

这样就得到了正确结果，提交AC。

[Link 1]: https://blog.csdn.net/zandaoguang/article/details/100117263