通知 网站从因情语写改为晴雨,这个网站的模板也从calmlog_ex改为 whimurmur

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

87人浏览 / 0人评论 / | 作者:whisper  | 分类: 剑指offer2  | 标签: 剑指offer2  | 

作者:whisper

链接:https://www.proprogrammar.com/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;
    }
};

基本一样,不多说了(为什么两个人代码写得这么像)


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

点赞(1) 打赏

全部评论

还没有评论!
广告位-帮帮忙点下广告