把n个骰子扔在地上，所有骰子朝上一面的点数之和为s。输入n，打印出s的所有可能的值出现的概率。
思路一：
统计每个骰子的点数，然后求和。使用深度优先遍历，用一个数组记录每个骰子的点数，第一个骰子的点数有6种可能，记录一种，然后记录下一个骰子的点数，下一个骰子同样有6种，和上一个骰子同样操作。当最后一个骰子的点数记录完毕之后，统计数组的和，此和出现的次数加一。
代码：
class Solution {
private:
vector<int> sum;
vector<double> count;
public:
void dfs(int n, int cur) {
if(cur == n) {
int su = 0;
for(int i = 0;i < n;i++) {
su += sum[i];
}
count[su-n] += 1.0;
return;
}
for(int i = 1;i <= 6;i++) {
sum[cur] = i;
dfs(n,cur+1);
}
}
vector<double> dicesProbability(int n) {
sum.resize(n);
count.resize(5*n+1);
dfs(n,0);
for(int i = 0;i < 5*n+1;i++) {
count[i] /= pow(6,n);
}
return count;
}
};思路二：
动态规划。记dp[i][j]表示i个骰子的和为j的概率。则有dp[i][j] = sum(d[i-1][j-k]),k=[1,6]。初始值dp[1][k] = 1/6,k=[1,6]。从1个骰子开始推，逐步推到第n个骰子。答案就是dp[n][k],k =[n,6n]。代码如下。
代码：
class Solution {
public:
vector<double> dicesProbability(int n) {
vector<vector<double>> dp(n+1,vector<double>(6*n+1));
for(int i = 1;i <= 6;i++) {
dp[1][i] = 1.0/6.0;
}
for(int i = 2;i <= n;i++) {
for(int j = i-1;j <= 6*(i-1);j++) {
for(int k = 1;k <= 6;k++) {
dp[i][j+k] += dp[i-1][j] / 6.0;
}
}
}
vector<double> ans;
for(int i = n;i <= 6*n;i++){
ans.push_back(dp[n][i]);
}
return ans;
}
};思路三：
状态压缩，思路二推导过程中，dp[i]只和dp[i-1]有关，所以可以用两个数组来压缩空间，轮番使用两个数组。
代码
class Solution {
public:
vector<double> dicesProbability(int n) {
vector<double> dp(6,1.0/6.0);
for(int i = 2;i <= n;i++) {
vector<double> tmp(5*i+1);
for(int j = 0;j < 5*(i-1)+1;j++) {
for(int k = 0;k < 6;k++) {
tmp[j+k] += dp[j] / 6.0;
}
}
dp = tmp;
}
return dp;
}
};