剑指Offer_#60_n个骰子的点数

剑指Offer_#60_n个骰子的点数

剑指offer

Contents

题目

把n个骰子扔在地上,所有骰子朝上一面的点数之和为s。输入n,打印出s的所有可能的值出现的概率。
你需要用一个浮点数数组返回答案,其中第 i 个元素代表这 n 个骰子所能掷出的点数集合中第 i 小的那个的概率。
示例 1:

输入: 1
输出: [0.16667,0.16667,0.16667,0.16667,0.16667,0.16667]

示例 2:

输入: 2
输出: [0.02778,0.05556,0.08333,0.11111,0.13889,0.16667,0.13889,0.11111,0.08333,0.05556,0.02778]

限制:

1 <= n <= 11

思路分析

这一题根本不是简单题...感觉是一道比较复杂的动态规划问题,书上的代码我也没有看懂,主要参考了题解:java 递归+记忆化递归+动态规划

可以观察到的规律

首先我们可以考虑比较最简单的几个例子,即n=1,2,3时的情况,可以得出一些结论:

  • 骰子数是n,那么点数和的范围是[n,6n]
  • 计算点数和为k的概率时(k∈[n,6n]),分母是所有骰子点数的全排列,即6n;分子是所有点数和为k的排列数。

分母是固定的,那么问题的关键就在于分子的计算,即如何统计出点数和为k的所有排列个数。
分析这个问题,比较自然的思路是递归的思路,然后对递归算法进行优化,可以得出动态规划的解法。

方法1:递归

我们可以将问题抽象出来,设定一个函数f(n,k),表示有n个骰子,出现的点数之和是k的所有组合数。
如何计算f(n,k)的值?我们可以这么考虑,n个骰子的点数和可以拆分为两部分,n-1个骰子的点数和与1个骰子的点数和,两部分相加结果一定是f(n,k)

  • 1个骰子出现的点数和最简单,一定是1~6当中的一个。
  • 根据那1个骰子的点数,我们可以推断出另外n-1个骰子的点数和,这两部分是互补的,有6种可能性。
    • 1 + (k-1)
    • 2 + (k-2)
    • 3 + (k-3)
    • 4 + (k-4)
    • 5 + (k-5)
    • 6 + (k-6)

也就是说,f(n,k)是骰子数为n,点数和为k的情况,是由骰子数为n-1的情况转变过来的。但骰子数为n-1时,点数和是不固定的,有6种可能性,即k-1,k-2...k-6。
得出递推关系:

f(n,k) = f(n-1,k-1)+f(n-1,k-2)+...+f(n-1,k-6)

即每个递归问题的解决要依赖于6个递归子问题。
然后考虑终止条件:
终止条件应该是f(1,x) = 1,即当骰子数为1时,组合数是1。
但这么写的话,无法处理x计算出负数的情况。所以代码中换了一种写法,是等效的,且避免了x为负数的情况,见代码注释。
最后是递归返回值:
返回f(n,k)
递归的思路是从上到下的,从f(n,k)开始,递归调用f(n-1,x),f(n-2,x)...直到满足终止条件,开始回溯,最后回到f(n,k)。

方法2:动态规划

递归的问题在于这里边有很多的重复计算,很多递归子问题是相同的,其实只需要计算一次。
动态规划是从下到上解决问题,先计算子问题的结果,将子问题的结果保存起来,那么后续计算时避免了重复计算。保存子问题结果的就是dp数组。
状态定义
dp(n,k),表示有n个骰子,出现的点数之和是k的所有组合数。

初始状态

dp(1,x) = 1

状态转移方程

dp(n,k) = dp(n-1,k-1)+dp(n-1,k-2)+...+dp(n-1,k-6)

其实思路是和递归几乎完全相同的,仅仅是修改了解决问题的顺序,就优化了时间复杂度。
更多细节请参考代码,写了很多注释。

解答

解法1:递归

class Solution {
    public double[] twoSum(int n) {
        //点数和总共有6n-n+1种情况,即[n...6n]
        double[] res = new double[5*n + 1];
        int curSum = n;
        for(int i = 0;i < res.length;i++){
            //计算每种点数和的概率,分母6^n是总的排列数,分母是出现各种点数和的排列数
            res[i] = countSum(curSum, n) / Math.pow(6, n);
            //res[0]对应的点数和是n,i增加时对应的点数和同步增加
            ++curSum;
        }
        return res;
    }

    private int countSum(int curSum, int n){
        if(n < 0 || curSum < 0) return 0;
        //任何一个curSum调用总是会分解到f(0,0),f(1,0),f(2,0)...
        //其中只有f(0,0)是1,其他的进一步分解必然出现负数,即得到0
        if(n == 0 && curSum == 0) return 1;
        int sum = 0;
        for(int i = 1;i <= 6;i++){
            sum += countSum(curSum-i, n-1);
        }
        return sum;
    }
}

递归写法对于n比较小的情况可以通过,n=9开始,时间超出限制。

解法2:动态规划

基本的dp解法,即用一个二维数组保存dp状态。

class Solution {
    public double[] twoSum(int n) {
        //把第0个位置空出来,目的是将数组索引与实际的骰子数目及点数对应
        int[][] dp = new int[n + 1][6*n + 1];
        //初始状态,即矩阵的第一行
        //每一行都依赖于上一行进行计算
        //这里循环变量用j比较合适,因为表示处理的是一行当中的每个元素
        for(int j = 1;j <= 6;j++) dp[1][j] = 1;
        //状态转移,由第一行开始,计算后面的所有行
        for(int i= 2;i <= n;i++){
            //因为i代表骰子数目,则其点数和范围应该是[i...6i]
            //进到第二层循环,即计算某一行当中的某个特定元素
            for(int j = i;j <= 6*i;j++){
                //用for循环表示状态转移方程,看起来会比较抽象,但是实际上并没有很难,不要害怕
                //实际上就是dp[i][j] = dp[i-1][j-1]+dp[i-1][j-2]+...+dp[i-1][j-6]
                //抽象出来,就是dp[i][j - dice],dice作为循环变量,每次累加一个dp[i][j - dice]
                for(int dice = 1;dice <= 6;dice++){
                    //j - dice = 0时,矩阵中的数字是无意义的,因为所有赋值都是从dp[1][1]开始的
                    if(j - dice <= 0) break;
                    dp[i][j] += dp[i - 1][j - dice];
                }
            }
        }
        double[] res = new double[5*n + 1];
        //dp[][n]开始计算,因为不存在点数和小于n的情况
        int j = n;
        //所有的排列数,即计算概率的分母
        double sum = Math.pow(6,n);
        //这里用k是因为这里遍历的是res[],而不是dp[][],加以区分
        for(int k = 0;k <= res.length - 1;k++){
            //迭代到最后,其实只需要看矩阵dp[][]当中最后一行(即第n行)的结果即可,代表的就是n个骰子各种点数和出现的次数
            //除以总的排列数,即得到概率
            res[k] = dp[n][j++] / sum;
        }
        return res;
    }
}

这个代码的提交成绩是双百。但是还有优化余地,因为dp矩阵当中,其实每一次只用得到当前行(dp[i][])和上一行(dp[i-1][]),所以不必要保存整个矩阵,只需要保存两行即可。

上一篇:LeetCode 643. 子数组最大平均数 I


下一篇:Maven仓库概述