# 面试题60

把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

## Solutions

1. **dynamic programming**
2. Count the number of cases with sum equals to values(sums) ranging from `n` to `n * 6` after rolled `n` times.
3. Then the propability of each `value(sum)` is `count * pow(1.0/6, n)`. ie: totoal number of combinations is `6^n`
4. `dp[n][i]` represents the number of cases with sum equals to `i` after we rolled `n` times.
   * Then `dp[n + 1][i] = dp[n][i - 6](current dice is 6) + dp[n][i - 5](current dice is 5) + .... dp[n][i - 1]`.

```cpp
class Solution {
public:
    vector<double> twoSum(int n) {
        vector<int> dp(n * 6 + 1, 0);
        for (int i = 1; i <= 6; i++)
            dp[i] = 1;

        for (int i = 2; i <= n; i++) {
            // traverse backwards to avoid overwrite data in dp table of the last time
            for (int sum = i * 6; sum >= i; sum--) {
                // Caution, must use a temporal varaible
                int cnt = 0;
                for (int cur = 1; cur <= 6; cur++) {
                    int prev = sum - cur;
                    if (prev < i - 1 || prev > (i - 1) * 6)
                        continue;
                    cnt += dp[prev];
                }
                dp[sum] = cnt;
            }
        }

        vector<double> res;
        double base = pow(1.0 / 6, n);
        for (int sum = n; sum <= n * 6; sum++)
            res.push_back(dp[sum] * base);

        return res;
    }
};
```


---

# Agent Instructions: Querying This Documentation

If you need additional information that is not directly available in this page, you can query the documentation dynamically by asking a question.

Perform an HTTP GET request on the current page URL with the `ask` query parameter:

```
GET https://zhongquan789.gitbook.io/leetcode/lcof/mian-shi-ti-60.md?ask=<question>
```

The question should be specific, self-contained, and written in natural language.
The response will contain a direct answer to the question and relevant excerpts and sources from the documentation.

Use this mechanism when the answer is not explicitly present in the current page, you need clarification or additional context, or you want to retrieve related documentation sections.