n个骰子的点数
题目描述
把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
解法：
本质上是求 n 个骰子的和为 s 时，一共有多少种可能。每种可能的数量除以总的可能数就得到了概率，所以知道了各种点数之和可能的数量，就可以算出对应的概率。
求 n 个骰子和为 s 的数量时，可以把 n-1 个骰子和为 s-1, s-2, s-3, ..., s-6 的可能累加起来。最底层，1 个骰子和为 1 2 3 4 5 6 时的可能数都是 1。
设置 f(n, s) 为 n 个骰子的和为 s 的组合数量，可以得到一下递推关系:
if n <= s <= n * 6:
f(n, s) = sum( f(n-1, s-i) for i in range(1, 6) )
else:
f(n, s) = 0
得到 n 个骰子构成的不同点数只和 s 的可能数后，就可以求出概率了。
根据以上思想可以写入如下代码：
class Solution {
public:
vector<double> twoSum(int n) {
vector<vector<int>> dp(n+1, vector<int>(n*6+1, 0));
for(int s=1;s<=6;s++){
dp[1][s] = 1;
}
// touzi: 骰子
for(int n_touzi = 2; n_touzi <= n; n_touzi++){
for(int s = n_touzi; s <= n_touzi * 6; s++){
for(int i = 1; i<=6; i++){
if(s - i > 0){
dp[n_touzi][s] += dp[n_touzi-1][s-i];
}
}
}
}
vector<double> ret;
double total = pow(6, n);
for(int s = n; s <= n * 6; s++){
ret.push_back(dp[n][s] / total);
}
return ret;
}
};
分析 dp 矩阵，你会发现下一行只依赖于上一行，因此可以对矩阵进行压缩，压缩后只用一个向量就够了。
class Solution {
public:
vector<double> twoSum(int n) {
vector<vector<int>> dp(n+1, vector<int>(n*6+1, 0));
for(int s=1;s<=6;s++){
dp[0][s] = 1;
}
for(int n_touzi = 2; n_touzi <= n; n_touzi++){
for(int s = n_touzi; s <= n_touzi * 6; s++){
for(int i = 1; i<=6; i++){
if(s - i > 0){
dp[n_touzi][s] += dp[n_touzi-1][s-i];
}
}
}
}
vector<double> ret;
double total = pow(6, n);
for(int s = n; s <= n * 6; s++){
ret.push_back(dp[n][s] / total);
}
return ret;
}
};
leetcode 上给这个题的函数的命名让人感到莫名其妙。