当前位置：
  1. 首页
  2. 剑指offer刷题第四期
  3. 问题详情

【动态规划专题】剑指 Offer 60. n个骰子的点数

本问题对应课程链接：剑指offer刷题第四期

要求：

1、请打卡你的解题代码，如果能简单说一下思路则简单说一下思路。
2、给出你代码所用的时间复杂度和空间复杂度

shuaidi
106 8

共以下 8 个回答

  • June 普通 2023年11月13日 上午11:36 
    class Solution {
    public double[] statisticsProbability(int num) {

        double[] dp = new double[6];
        for(int i=0;i<6;i++)
            dp[i] = 1.0/6.0;
        for(int i = 2; i <= num ; i++) // 来了第几个骰子
        {
            double[] tmp = new double[5 * i + 1];  //再来一个骰子，拼接数组，由于n个骰子不存在点数总和小于 n ,所以是 5 * i + 1
            for(int j = 0; j < dp.length; j++)
            {
                for(int k=0; k < 6; k++)
                {
                    tmp[j + k] += dp[j] / 6.0;
                }
            }
            dp = tmp;
        }
        return dp;
    }
}
    0 赞同 0 条回复
  • Marshan 普通 2023年9月3日 上午10:14

    没到过自己想还真想不出来

    class Solution {
public:
    vector<double> dicesProbability(int n) {
        vector<vector<int>> dp(n+1,vector<int>(6*n+1));
        // dp[i][j]表示i个骰子时,点数为j的情况数

        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];
                }
            }
        }

        int sum = pow(6,n);
        vector<double> res(5*n+1);
        int index = 0;
        for(int i = n;i <= 6*n;++i){
            res[index++] = (double)dp[n][i] / sum;
        }
        return res;
    }
};
    0 赞同 0 条回复
  • 北辰 普通 2023年8月25日 上午11:57 
    class Solution {
    public double[] dicesProbability(int n) {
        int[][] dp = new int[n+1][6*n+1];
        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

    时间复杂度：O（n^2）
    空间复杂度：O（n）

    0 赞同 0 条回复
  • Mby 普通 2023年8月21日 下午4:41 
    class Solution {
    public double[] dicesProbability(int n) {
        int[][] dp = new int[n+1][6*n+1];

        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];
                }
            }
        }

        double[] res = new double[5*n + 1];
        int index = 0;
        double sum = Math.pow(6,n);

        for(int i = n; i <= 6 * n; i++){
            res[index++] = dp[n][i] / sum;
        }

        return res;
        //时间复杂度：O(n^2)
        //空间复杂度：O(n)
    }
}
    0 赞同 0 条回复
  • mpweixin用户 普通 2023年8月21日 下午3:36 
    动态规划
double[] dp = new double[6];
        Arrays.fill(dp, 1.0 / 6.0);
        for (int i = 2; i <= n; i++) {
            double[] tmp = new double[5 * i + 1];
            for (int j = 0; j < dp.length; j++) {
                for (int k = 0; k < 6; k++) {
                    tmp[j + k] += dp[j] / 6.0;
                }
            }
            dp = tmp;
        }
        return dp;
    0 赞同 0 条回复
  • 人生何处不青山 普通 2023年8月20日 下午11:01

    背

    function dicesProbability(n: number): number[] {
    let dp: number[] = new Array(6);
    dp.fill(1 / 6);
    for (let i = 2; i <= n; i++) {
        let tmp:number[] = new Array(5 * i + 1).fill(0);
        for (let j = 0; j < dp.length; j++) {
            for (let k = 0; k < 6; k++) {
                tmp[j + k] += dp[j] / 6;
            }
        }
        dp = tmp;
    }
    return dp;
};
    0 赞同 0 条回复
  • 阿尚 普通 2023年8月9日 下午9:02 
    class Solution {
    public double[] dicesProbability(int n) {
        int min = n; // n 个骰子掷出的最小值
        int max = 6* n; // n 个骰子掷出的最大值

        //dp定义：i 个骰子掷出 j 的概率为dp[i][j]
        double[][] dp = new double[n + 1][max + 1];

        //初始化：一个骰子掷出 1 ~ 6 的概率都是 1 / 6
        for(int i = 1; i <= 6; i++){
            dp[1][i] = 1 / 6.0;
        }

        for(int i = 2; i <= n; i++){
            for(int j = i; j <= 6 * i; j++){
                //递推公式
                for(int k = 1; k <= 6 && k < j; k++){
                    dp[i][j] += dp[i - 1][j - k] * (1 / 6.0);
                }
            }
        }

        double[] res = new double[max - n + 1];
        for(int i = 0; i < res.length; i++){
            res[i] = dp[n][min + i];
        }

        return res;
    }
}
    0 赞同 0 条回复
  • 长河呼叫黄江 普通 2023年8月9日 上午8:41

    8.8 周二
    Day29：下面是代码

    class Solution {
    public double[] dicesProbability(int n) {
        //初始化dp
        double[] dp = new double[6];
        Arrays.fill(dp, 1.0 / 6.0);
        for(int i = 2; i <= n; i++){
            double[] tmp = new double[5 * i + 1];
            for(int j = 0; j < dp.length; j++){
                for(int k = 0; k < 6; k++){
                    tmp[j + k] += dp[j] * (1.0 / 6.0);
                }
            }
            dp = tmp;
        }
        return dp;
    }
}
    0 赞同 0 条回复

# 回答此问题

后才能回答