n个骰子的点数

这题出自 LeetCode
,题目如下:

把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个骰子所能得到的不同排列次数是固定的,即

\[N = 6^n \]

那么问题转换成用n个骰子组成和为s的不同排列次数有多少种,可以记为 f(n,s) 。此时,我们可以想象把这n个骰子分成两堆,一堆有n-1个,另一堆只有1个。显然,1个骰子掷出1的可能性只有1种,同样,掷出2、3、4、5、6的可能性也只有1种。那么问题转化成了:

\[f(n,s) = \sum_{i=1}^{6}f(n,s-i) \]

容易知道, f(1,1),f(1,2),...f(1,6) = 1 。我们可以先把这些边界值填上,然后不断地往上计算,就能得到最终的 f(n,s) 。代码如下:

class Solution {
public:
vector<double> dicesProbability(int n) {
int m = n * 6;
int **a = new int *[m + 1];
for(int i = 0; i < m + 1; i++)
{
a[i] = new int[n + 1];
for(int j = 0; j < n + 1; j++)
{
a[i][j] = 0;
}
}
for(int i = 1; i <= m; i++)
{
if(i <= 6)
{
a[i][1] = 1;
}
else
{
a[i][1] = 0;
}
}
for(int j = 2; j < n; j++)
{
a[1][j] = 0;
}
for(int i = 2; i <= m; i++)
{
for(int j = 2; j <= n; j++)
{
a[i][j] = calc(a, i, j);
}
}
int all = 1;
for(int j = 1; j <= n; j++)
{
all *= 6;
}
vector<double> res;
for(int i = 1; i <= m; i++)
{
if(a[i][n] != 0)
{
res.push_back(a[i][n] / (all * 1.0));
}
}
return res;
}
int calc(int **a, int m, int n)
{
int sum = 0;
for(int i = 1; i <= 6; i++)
{
if(m - i > 0)
{
sum += a[m - i][n - 1];
}
}
return sum;
}
};

值得一提的是,可以看出我们的公式计算实际上只依赖前一个状态,所以其实并不需要二维存储空间,使用一维数组就能解决问题。

class Solution {
public:
vector<double> dicesProbability(int n) {
int *a = new int[6 * n + 1];
for(int i = 0; i <= 6 * n; i++)
{
a[i] = 0;
}
for(int i = 1; i <= 6; i++)
{
a[i] = 1;
}
for(int i = 2; i <= n; i++)
{
for(int j = 6 * i; j >= i; j--)
{
int s = j - 6;
if(s <= i - 1)
{
s = i - 1;
}
a[j] = 0;
for(int k = s; k <= j - 1; k++)
{
a[j] += a[k];
}
}
}
vector<double> res;
int all = 1;
for(int i = 1; i <= n; i++)
{
all *= 6;
}
for(int i = n; i <= 6 * n; i++)
{
if(a[i] != 0)
{
res.push_back(a[i] / (all * 1.0));
}
}
return res;
}
};

注意一点,在计算 f(n, s)
时,数组前面6个 f(n - 1, s - 1), ..., f(n - 1, s - 6)
不一定都是有效的值,因为在计算 f(n - 1, s)
时,我们是从 s = n - 1
的情况下开始算的,这也好理解,毕竟n - 1个骰子掷出的最小点数之和必定是n - 1。所以我们在计算 f(n, s)
时要从第一个有效的值开始算起,即 min(n - 1, s - 6)
。否则可能会把前几次计算遗留下的脏值给错误计算进去,得到不正确的结果。

博客园精华区
我还没有学会写个人说明!
上一篇

彻底搞明白mybatis缓存(上)

下一篇

关于 PostgreSQL 全文检索的实战 —— 中文分词、查询、索引、权重、排序

你也可能喜欢

评论已经被关闭。

插入图片