剑指Offer-60.n个骰子的点数

Posted on | In

刚开始看题目半天没看明白题目在说啥，看懂之后发现这是一道很经典的DP问题。

面试题60. n个骰子的点数

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

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

示例 1:

1
2
3
> 输入: 1
> 输出: [0.16667,0.16667,0.16667,0.16667,0.16667,0.16667]
>

示例 2:

1
2
3
> 输入: 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

思路:

求解出现的概率，点数k的概率公式为: p(k) = k 出现的次数 / 总次数

由于是投掷n个骰子，总次数为6n 。

所以我们现在将问题转化为求k出现的次数。

dp问题的四部曲：1.确定状态 2.状态方程 3.边界处理 4.顺序处理

  1. 确定状态，主要是找最后阶段。本题的最后阶段是要求解n个骰子，每个点数出现的和。我们这里就可以假设n=2，如果求解8点出现的次数，可以有很多种组合比如[2, 6] [6, 2] [4, 4] [4, 4]，这里我们就需要将上一阶段的点数保存下来。

  2. 转移方程：dp [i] [j] += dp [i - 1] [j - cur] ， i表示第几颗骰子， j表示现在的总点数之和，cur表示第i次投掷骰子出现的点数。例如第2颗骰子为4 ，dp [2] [8] += dp [1] [8-4] 。

  3. 初始化： 初始化,一颗骰子的时，1-6只出现一次。

  4. 顺序求解。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
class Solution {
public:
    vector<double> twoSum(int n) {
        vector<vector<int>> dp(n + 1, vector<int>(6*n + 1));
        for(int i = 1; i <= 6; ++i)         // 初始化,一颗骰子的时,1-6只出现一次
            dp[1][i] = 1;
        for(int i = 2; i <= n; ++i){
            for(int j = i; j <= 6*n; ++j){
                for(int cur = 1; cur <= 6; ++cur){
                    if(j <= cur)
                        break;
                    dp[i][j] += dp[i-1][j-cur];
                }
            }
        }
        vector<double> ans;
        int power = pow(6,n);			//总点数
        for(int i = n; i <= 6 * n; ++i)
            ans.emplace_back((double)dp[n][i] / power);
        return ans;
    }
};