本文共 1156 字，大约阅读时间需要 3 分钟。

题目

把n个骰子扔在地上，所有骰子朝上一面的点数之和为s。输入n，打印出s的所有可能的值出现的概率。

你需要用一个浮点数数组返回答案，其中第 i 个元素代表这 n 个骰子所能掷出的点数集合中第 i 小的那个的概率。

思路

初见就没弄懂题目什么意思，看题解也不是很明白，后来自己弄懂了。

首先，n 枚骰子掷出的点数的范围是 [n, 6*n]，根据排列组合，所有投掷的总可能性是

这道题可以使用DP

分解状态时，我们理解为每一次投掷一个骰子，然后把之前的结果加起来，用二维数组保存之前的状态，就可以避免递归重复计算的问题，降低时间复杂度。

以下数组格子里是出现次数可能的编号，而不是出现次数

第一次

第二次

这就可以解释代码中的

这个部分的作用

更具体的解释见书上294页或题解：

代码

class Solution {public:    vector
   
     twoSum(int n) {        vector
    
      ret;        int dp[15][70]; //n<=11 最大6*11=66        memset(dp, 0, sizeof(dp));        //初始状态设置好，第一个骰子，六个面，每个面出现的次数为1        for (int i = 1; i <= 6; i ++) {            dp[1][i] = 1;        }        for (int i = 2; i <= n; i ++) {            for (int j = i; j <= 6*i; j ++) {                for (int cur = 1; cur <= 6; cur ++) {                    if (j - cur <= 0) {                        break;                    }                    dp[i][j] += dp[i-1][j-cur];                }            }        }        //总数是6^n        int all = pow(6, n);                for (int i = n; i <= 6 * n; i ++) {            ret.push_back(dp[n][i] * 1.0 / all);        }        return ret;    }};
    
   

转载地址：https://blog.csdn.net/hanmin822/article/details/106154235 如侵犯您的版权，请留言回复原文章的地址，我们会给您删除此文章，给您带来不便请您谅解！