数据结构学习 jz60 n个骰子的点数

本文主要是介绍数据结构学习 jz60 n个骰子的点数，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

关键词：动态规划 滚动数组优化

这道题还是不难的，就是特别纠结要怎么优化这个存储空间以及动态规划的方法，因为我觉得这个方法好原始，最后决定不优化了。最后发现题解也是这个原始的样子，我就放心了。用时38min。

题目：

 思路：

类似跳楼梯，一次可以跳1-6级。

dp状态：

dp[i][j]：第i次抛筛子，第j小的点数集合的概率。

转移方程：

dp[i][j]=(dp[i-1][j-1]+dp[i-1][j-2]+...+dp[i-1][j-6])*(1/6)【这里注意范围】

i-1次抛筛子的集合点数的概率*1/6

初始化：第一次抛骰子，所有点数的概率都是1/6

复杂度计算：

时间复杂度O(n^2)

空间复杂度O(n)

代码：

我的dp状态的长度是num*6+1，因为想要dp的索引对应点数的集合。

抛第i次的时候，最大的点数集合是i*6，最小的点数集合是i。

class Solution {
public:vector<double> statisticsProbability(int num) {vector<double> dp(6*num+1,1.0/6);dp[0]=0;for(int i=2;i<=num;++i){for(int j=i*6;j>=i;--j){dp[j]=0;for(int z=1;z<=6;++z){if(j-z>=i-1&&j-z<=(i-1)*6)//从上一轮里面选dp[j]+=dp[j-z];}dp[j]*=1.0/6;}}vector<double> res(num*5+1);int j=0;for(int i=num;i<=num*6;++i,++j){res[j]=dp[i];}return res;}
};

这篇关于数据结构学习 jz60 n个骰子的点数的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---