❓ 剑指 Offer 60. 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
💡思路：动态规划
使用一个二维数组
dp
存储点数出现的次数，其中
dp[i][j]
表示前
i
个骰子产生点数
j
的次数。
只看第
n
枚骰子，它的点数可能为
1
,
2
,
3
,
...
,
6
，因此投掷完
n
枚骰子后点数
j
出现的次数，可以由投掷完
n−1
枚骰子后，对应点数
j−1
,
j−2
,
j−3
,
...
,
j−6
出现的次数之和转化过来。
for(第n枚骰子的点数 k =1; k <=6; k++){
dp[n][j]+= dp[n-1][j - k]}
写成数学公式是这样的：
d
p
[
n
]
[
j
]
=
∑
i
=
1
6
d
p
[
n
−
1
]
[
j
−
k
]
dp[n][j]=\sum_{i=1}^6dp[n-1][j-k]
dp[n][j]=i=1∑6dp[n−1][j−k]
n
表示阶段，
j
表示投掷完
n
枚骰子后的点数和，
k
表示第
n
枚骰子会出现的六个点数。
⭐️ 空间优化： 旋转数组
观察发现每个阶段的状态都只和它前一阶段的状态有关，因此我们不需要用额外的一维来保存所有阶段。
- 用两个一维数组交替变换存储。
🍁代码：(C++、Java)
C++
classSolution{public:
vector<double>dicesProbability(int n){int maxsum = n *6;
vector<vector<longlong>>dp(n +1,vector<longlong>(maxsum +1));for(int i =1; i <=6; i++){
dp[1][i]=1;}for(int i =2; i <= n; i++){for(int j = i; j <= i *6; j++){for(int k =1; k <=6&& k <= j; k++){
dp[i][j]+= dp[i -1][j - k];}}}longlong totalnum =pow(6, n);
vector<double>ans(n *5+1);for(int i = n; i <= maxsum; i++){
ans[i - n]=(double)dp[n][i]/ totalnum;}return ans;}};
⭐️ 空间优化： 旋转数组
C++
classSolution{public:
vector<double>dicesProbability(int n){int maxsum = n *6;
vector<vector<longlong>>dp(2,vector<longlong>(maxsum +1));for(int i =1; i <=6; i++){
dp[0][i]=1;}int flag =1;//旋转标记for(int i =2; i <= n; i++, flag =1- flag){for(int j =0; j <= i *6; j++){
dp[flag][j]=0;//旋转数组清零}for(int j = i; j <= i *6; j++){for(int k =1; k <=6&& k < j; k++){
dp[flag][j]+= dp[1- flag][j - k];}}}longlong totalnum =pow(6, n);
vector<double>ans(n *5+1);for(int i = n; i <= maxsum; i++){
ans[i - n]=(double)dp[1- flag][i]/ totalnum;}return ans;}};
Java
classSolution{publicdouble[]dicesProbability(int n){int maxsum = n *6;long[][] dp =newlong[2][maxsum +1];for(int i =1; i <=6; i++){
dp[0][i]=1;}int flag =1;//旋转标记for(int i =2; i <= n; i++, flag =1- flag){for(int j =0; j <= i *6; j++){
dp[flag][j]=0;//旋转数组清零}for(int j = i; j <= i *6; j++){for(int k =1; k <=6&& k < j; k++){
dp[flag][j]+= dp[1- flag][j - k];}}}double totalnum =Math.pow(6, n);double[] ans =newdouble[n *5+1];for(int i = n; i <= maxsum; i++){
ans[i - n]= dp[1- flag][i]/ totalnum;}return ans;}}
🚀 运行结果：
🕔 复杂度分析：
- 时间复杂度： O ( n 2 ) O(n^2) O(n2)， 状态转移循环
n−1轮；每轮中，当i=2,3,...,n时，对应循环数量分别为6×6,11×6,...,[5(n−1)+1]×6；因此总体复杂度为 O ( ( n − 1 ) × 6 + [ 5 ( n − 1 ) + 1 ] 2 × 6 ) O((n−1)×\frac{6+[5(n-1)+1]}2×6) O((n−1)×26+[5(n−1)+1]×6)，即等价于 O ( n 2 ) O(n^2) O(n2)。 - 空间复杂度： O ( n ) O(n) O(n)，
dp数组需要2*n*6的空间，所以 O ( 2 ∗ n ∗ 6 ) = O ( n ) O(2n6) = O(n) O(2∗n∗6)=O(n)。
题目来源：力扣。
放弃一件事很容易，每天能坚持一件事一定很酷，一起每日一题吧！
关注我LeetCode主页 / CSDN—力扣专栏，每日更新！
注： 如有不足，欢迎指正！
本文转载自: https://blog.csdn.net/weixin_43412762/article/details/132481397
版权归原作者 酷酷的懒虫 所有， 如有侵权，请联系我们删除。
版权归原作者 酷酷的懒虫 所有， 如有侵权，请联系我们删除。