题目链接：剑指 Offer 60. n个骰子的点数
方法：动态规划
解题思路
- \(n = 1\) 时可能的和为 \([1, 6]\)，其概率为 \(dp[1][] = [1/6, 1/6, 1/6, 1/6, 1/6, 1/6]\)
- \(n = 2\) 时对于第一个骰子为 \(1\) 时，第二个骰子可以为 \([1, 6]\)，其可以构成的和为 \([2, 7]\)，分别为其中的和 \([i + j]\) 增加 \(dp[1][i] / 6\) 的概率，即 \(dp[2][i + j] += dp[1][i] / 6\)，其中 \(i = 1\)，表示第一个骰子为 \(1\)，\(j\) 为第二个骰子的值可以取 \([1, 6]\)；
- ...
- 由于每一层的 \(dp\) 数组的值只和上一层有关，因此可以优化为一维数组实现。
代码
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, 0);
for (int j = 0; j < dp.size(); j ++ ) {
for (int k = 0; k < 6; k ++ ) {
tmp[j + k] += dp[j] / 6.0;
}
}
dp = tmp;
}
return dp;
}
};
复杂度分析
时间复杂度：\(O(n^2)\)；
空间复杂度：\(O(n)\)。