作者：

链接：http://proprogrammar.com:443/article/859

声明：请尊重原作者的劳动，如需转载请注明出处

剑指 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

难度：中等；标签：无；编程语言：C++

我的解法

class Solution {
public:
    vector<double> dicesProbability(int n) {
        int dp[70];
        memset(dp, 0, sizeof(dp));
        for (int i = 1; i <= 6; i ++) {
            dp[i] = 1;
        }
        for (int i = 2; i <= n; i ++) {
            for (int j = 6*i; j >= i; j --) {
                dp[j] = 0;
                for (int cur = 1; cur <= 6; cur ++) {
                    if (j - cur < i-1) {
                        break;
                    }
                    dp[j] += dp[j-cur];
                }
            }
        }
        int all = pow(6, n);
        vector<double> ret;
        for (int i = n; i <= 6 * n; i ++) {
            ret.push_back(dp[i] * 1.0 / all);
        }
        return ret;
    }
};

动态规划解法，一个骰子时情况是知道的，那么如果n-1，n-2，...1个骰子时是知道的，那么n的骰子的情况，第n个骰子可以掷1~6点，n个骰子可能点数是n~6n点，对n个骰子掷j点的情况，如果第n个骰子掷cur点，那么剩下n-1个应该掷j-cur点，共dp[j-cur]种情况，注意到如果j<cur+i-1，是不可能的，就是j太小，cur太大，就算其实n-1个骰子都掷1点，还是不行，举个例子，如n=10个骰子，j=10，cur当前掷2点，那么其它9个骰子n-1(i-1)至少9点，10<cur+i-1=11，是不可能的，提前break

其它解法

class Solution {
public:
    vector<double> dicesProbability(int n) {
        int dp[n+1][6*n+1];
        memset(dp, 0, sizeof(dp));
        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 k = 1; k <= 6; k++){
                    if(j <= k)break;
                    dp[i][j] += dp[i - 1][j - k];
                }
            }
        }
        vector<double> ans;
        double all = pow(6, n);
        for (int i = n; i <= 6 * n; i++){
            ans.push_back(1.0*dp[n][i]/all);
        }
        return ans;
    }
};

基本一样，不多说了（为什么两个人代码写得这么像）

亲爱的读者：有时间可以点赞评论一下