【LeetCode-动态规划】n个骰子的点数

题目描述

把n个骰子扔在地上，所有骰子朝上一面的点数之和为s。输入n，打印出s的所有可能的值出现的概率。
你需要用一个浮点数数组返回答案，其中第 i 个元素代表这 n 个骰子所能掷出的点数集合中第 i 小的那个的概率。
示例：

输入: 1
输出: [0.16667,0.16667,0.16667,0.16667,0.16667,0.16667]

说明： 1 <= n <= 11
题目链接： https://leetcode-cn.com/problems/nge-tou-zi-de-dian-shu-lcof/

思路

对于 n 个骰子来说，s 的范围为 [n, 6*n]。使用动态规划来做：

• 状态定义：dp[i][j] 表示使用 i 个筛子得到点数和为 j 的次数；
• 边界条件：dp[1][j] = 1，j ∈ [1, 6]，因为 1 个筛子出现的点数之和在 1 到 6 之间，且出现的概率相等；
• 状态转移：投掷第 n 个骰子后，s 为 j 的次数 dp[n][j] 可以从第 n-1 投掷中推出。因为投掷第 n 个骰子得到的点数范围为 [1, 6]，所以有 \(dp[i][j] = \sum_{i=1}^6 dp[i-1][j-i]\)。也就是，第 n 枚骰子，它的点数可能为 1 , 2, 3, ... , 6，因此投掷完 n 枚骰子后点数 j 出现的次数，可以由投掷完 n-1 枚骰子后，对应点数 j-1, j-2, j-3, ... , j-6出现的次数之和转化过来。

用代码描述状态转移：

for (第n枚骰子的点数 i = 1; i <= 6; i ++) {
    dp[n][j] += dp[n-1][j - i]
}

完整代码如下：

class Solution {
public:
    vector<double> twoSum(int n) {
        vector<vector<int>> dp(12, vector<int>(12*6, 0));
        for(int i=1; i<=6; i++) dp[1][i] = 1;  // 边界条件
        for(int i=2; i<=n; i++){
            for(int j=i; j<=i*6; j++){
                for(int cur=1; cur<=6; cur++){
                    if(j-cur<=0) break;
                    dp[i][j] += dp[i-1][j-cur];
                }
            }
        }

        vector<double> ans;
        double all = pow(6, n);  // 总次数
        for(int i=n; i<=6*n; i++) ans.push_back(dp[n][i]/all);
        return ans; 
    }
};

参考

https://leetcode-cn.com/problems/nge-tou-zi-de-dian-shu-lcof/solution/nge-tou-zi-de-dian-shu-dong-tai-gui-hua-ji-qi-yo-3/

【LeetCode-动态规划】n个骰子的点数

原文：https://www.cnblogs.com/flix/p/13398276.html