题目
把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]
解题
方法一：回溯(超时)
需要多少个n，就要多少次for循环，这显然是不行的，因此可以使用回溯，进行暴力循环。
题目中限制n最大为11，也就是O(n^11)复杂度，这个显然是会超时的。
class Solution { public: vector<int> count; void backtraing(int n,int k,int sum){ if(k==n){ count[sum]++; return; } for(int i=1;i<=6;i++){ sum+=i; backtraing(n,k+1,sum); sum-=i; } } vector<double> dicesProbability(int n) { count.resize(n*6+1);//可存储 结果为0~6*n 出现的次数 backtraing(n,0,0); vector<double> vec(count.begin()+n,count.end());//只需要结果为n~6*n double sum=accumulate(vec.begin(),vec.end(),0);//求和 for(double& num:vec) num/=sum;//计算概率 return vec; } };
方法二：动态规划
代码实现的注意点：
比如n=2的时候，和的范围是2 ~ 12,个数为11个，因此个数为5*n+1，每个值对应索引为0 ~ 5 * n
这样是为了节约空间。还可以利用dp.size()来控制循环。
class Solution { public: vector<double> dicesProbability(int n) { vector<double> dp(6,1/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; } };
