剑指Offer_#60_n个骰子的点数
剑指offerContents
题目
把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][]
),所以不必要保存整个矩阵,只需要保存两行即可。