【动态规划专题】剑指 Offer 60. n个骰子的点数-跟着帅地玩副业，开拓第二曲线PlayOffer

Gg 普通 2023年8月12日下午4:08

class Solution {
    // 1、暴力法，分母为6^n个，分子为[n,6n]个情况，6n-n+1 = 5n+1总情况 
    // 再分别求每个情况的个数 / 6^n
    // 1、动归。定义dp[]数组为 i个骰子,和为j。
    // 状态转移方程。dp[i][j] 为 dp[i-1][j-1] * 1/6 + dp[i-1][j-2] * 1/6 + 
    public double[] dicesProbability(int n) {
        double[] dp = new double[6];
        // n为1的情况
        Arrays.fill(dp,1.0/6.0);
        // n大于2的情况
        for(int i = 2; i <= n; i ++){
            double[] tmp = new double[i*5+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年3月19日下午10:08

class Solution {
    public double[] dicesProbability(int n) {
        //三层循环 骰子个数 dpi 6个数字
        double[] dp = new double[6];
        Arrays.fill(dp, 1.0 / 6.0);
        for(int i = 2; i <= n; i++){
            double[] temp = new double[5 * i + 1];
            for(int j = 0; j < dp.length; j++){
                for(int m = 0; m < 6; m++){
                    temp[j + m] += dp[j] / 6.0;
                }
            }
            dp = temp;
        }
        return dp;
    }
}

0 赞同 0 条回复

PatNick 普通 2023年1月20日下午4:33

def dicesProbability(n: int) -> list[float]:
    # 定义dp[i][j]含义：当骰子个数为i，点数之和为j时，有dp[i][j]中组合
    dp = [[0 for __ in range(6 * n + 1)] for _ in range(n + 1)]

    # n个骰子话，点数之和的取值范围是[n,6n],所以个数就是5n+1
    res = [0] * (5 * n + 1)
    # 初始化
    for _ in range(1, 7):
        dp[1][_] = 1

    for i in range(2, n + 1):
        # 注意这里点数和的取值范围是取决于骰子数i的
        for j in range(i, 6 * i + 1):
            # 递推式的含义：i个骰子点数和为j的组合数量可以等于i-1个骰子点数和为j-1的组合数加上一个"1"朝上的骰子，或者是i-1个骰子点数和为j-2的组合数加上一个"2"朝上的骰子，……
            dp[i][j] = dp[i - 1][j - 1] + dp[i - 1][j - 2] + dp[i - 1][j - 3] + dp[i - 1][j - 4] + dp[i - 1][j - 5] + \
                       dp[i - 1][j - 6]


    # n个骰子，朝上点数之和一共有6^n种组合
    total = pow(6, n)
    index = 0
    for _ in range(n, 6 * n + 1):
        # 计算每种点数和组合数占总组合数的比
        res[index] = dp[n][_] / total
        index += 1

    return res

0 赞同 0 条回复

lucca 普通 2023年1月19日下午10:13

DP一生之敌

class Solution {
    public double[] dicesProbability(int n) {
        double[][] f = new double[n + 1][6 * n + 1];
        for (int i = 1; i <= 6; i++) f[1][i] = 1.0 / 6;
        for (int i = 1; i < n; i++) {
            for (int j = i; j <= 6 * i; j++) {
                for (int k = 1; k <= 6; k++) {
                    f[i + 1][j + k] += f[i][j] / 6; 
                }
            }
        }
        double[] ans = new double[5 * n + 1];
        for (int i = n, j = 0; i <= 6 * n; i++, j++) {
            ans[j] = f[n][i];
        }
        return ans;
    }
}

0 赞同 0 条回复

@ 普通 2022年12月26日下午6:30

时间复杂度：O(n^2)
空间复杂度：O(n)

//暴力超时了，dp实在想不出来诶
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;
    }
}

0 赞同 0 条回复

T 普通 2022年12月3日上午10:03

下面代码

class Solution {
    public double[] dicesProbability(int n) {
        double[][] dp = new double[n + 1][n * 6 + 1];
        double[] res = new double[n * 5 + 1];
        for(int i = 1; i <= 6; i++) {
            dp[1][i] = 1.0 / 6;
        }

        for(int i = 2; i <= n; i++) {
            for(int j = i; j <= i * 6; j++) {
                for(int k = 1; k <=6; k++) {
                    if(j - k > 0) 
                        dp[i][j] += dp[i - 1][j - k] / 6;
                    else
                        break;
                }
            }
        }
        for(int i = 0; i <= n * 5; i++) {
            res[i] = dp[n][n + i];
        }
        return res;

    }
}

0 赞同 0 条回复

派大星普通 2022年12月2日下午11:20

class Solution {
//时间复杂度O(n^2)
    public double[] dicesProbability(int n) {
        int[][] dp = new int[n + 1][n * 6 + 1];
        for (int i = 1; i <= 6; ++i) {
            dp[1][i] = 1;
        }
        for (int i = 1; i <= n; ++i) {
            for (int j = i, t1 = i * 6; j <= t1; ++j) {
                for (int k = 1, t2 = Math.min(j, 6); k <= t2; ++k) {
                    dp[i][j] += dp[i - 1][j - k];
                }
            }
        }
        double[] res = new double[n * 5 + 1];
        double m = Math.pow(6, n);
        for (int i = 0, t = n * 5; i <= t; ++i) {
            res[i] = dp[n][n + i] / m;
        }
        return res;
    }
}

0 赞同 0 条回复

Tolkien 永久会员 2022年12月1日上午10:08

public static double[] dicesProbability(int n) {
        // n为骰子个数，6*n为n个骰子的和的取值范围
        double[][] dp = new double[n + 1][6 * n + 1];

        // 由于关系式中出现dp[i-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++) {
                // 遍历第i个骰子出现的可能值
                for (int k = 1; k <= 6; k++) {
                    if (j - k < 0) {
                        break;
                    }
                        dp[i][j] += dp[i - 1][j - k];
                }
            }
        }

        // 返回结果，将n个骰子，总和为i的结果放入result
        // result的大小为取值范围 6*n-n+1 = 5*n+1
        double[] result = new double[5*n+1];
        int index = 0;
        for (int i = n; i <= n*6; i++) {
            result[index++] = dp[n][i]/Math.pow(6,n);
        }

        return result;
    }

0 赞同 0 条回复

西西弗斯的石头永久会员 2022年11月27日下午4:36

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

class Solution {
    public double[] dicesProbability(int n) {
       int[] dp = new int[6*n+1];
       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 k = 1;k <= 6; k++){
                   if(j - k < i - 1) break; 
                   dp[j] += dp[j - k];
               }
           }
       }
       double[] res = new double[5*n + 1];
       double m = Math.pow(6,n);
       int index = 0;
       for(int i=n;i <=6*n;i++){
           res[index++] = dp[i]/m;
       }
       return res;
    }
}

0 赞同 0 条回复

Mooby 普通 2022年11月27日下午4:20

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 条回复

訁訁訁訁訁普通 2022年11月25日下午11:15

/**
时间空间复杂度均为O(n^2)
优化为一维的没想出来
使用二维数组：需要考虑骰子个数还有点数
dp[i][j]:有i个骰子的时候，点数为j时组合数有dp[i][j]种
关系式
dp[i][j]=dp[i-1][j-1]+dp[i-1][j-2]+...dp[i-1][j-6]
分别对应上一个骰子1      2         ...      6
初始化：
dp[1][1]=1,dp[1][2]=1...dp[1][6]=1;
 */
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++){
            //i个骰子时 s的取值范围为[i,6i]
            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];
                }
            }
        }
        //取值范围[n,6n]一个5n+1个元素
        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;
    }
}

0 赞同 0 条回复

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

共以下 11 个回答

DP一生之敌

# 回答此问题取消回复

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

共以下 11 个回答

DP一生之敌

# 回答此问题 取消回复

# 回答此问题取消回复