招舟子普通 2024年1月3日下午3:40

class Solution {
public double[] statisticsProbability(int num) {
int[][] dp = new int[num+1][6num+1];//当有i个骰子时有j个组合
for(int i=1;i<=6;i++){
dp[1][i] = 1;
}
for(int i=2;i<=num;i++){
for(int j=i;j<=6i;j++){
for(int t=1;t<7;t++){
if(j<t)break;
dp[i][j]+= dp[i-1][j-t];
}
}

    }
double[] res = new double[5*num+1];
double tmp = Math.pow(6,num);
int a= 0;

for(int i=num;i<=6*num;i++){
    res[a++]=dp[num][i]/tmp;
}
return res;
}

}

0 赞同 0 条回复

九号球普通 2023年12月9日下午6:09

“`java
class Solution {
public double[] statisticsProbability(int num) {
//只有一个骰子的时候，概率都是1/6，有两个骰子的时候
//骰子个数为n时，数字和的范围是[n,6n]，总个数为6n-n+1=5n+1
double[] dp = new double[6];
Arrays.fill(dp, 1.0/6.0);
for (int i = 2; i <= num; 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; } } dp = tmp; } return dp; } }

0 赞同 0 条回复

张开怀普通 2023年7月24日下午7:24

class Solution {
public:
    vector<double> dicesProbability(int n) {
        vector<vector<int>> dp(n+1, vector<int>(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];
                }
            }
        }

        vector<double> res(5*n + 1);
        int index = 0;
        double sum = pow(6, n);

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

        return res;
    }
};

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

0 赞同 0 条回复

Dsjh 普通 2023年7月23日下午8:25

MY

class Solution {
public:
    vector<double> dicesProbability(int n) {
        vector<vector<int>>dp(n+1,vector<int>(6*n+1,0));
        for(int i=1;i<=6;i++){
            dp[1][i] = 1;
        }
        // dp[i][j] = dp[i-1][j-1] +...+dp[i-1][j-6];
        // 个数为i，点数之和为j的组合数
        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)
                        dp[i][j] += dp[i-1][j-k];
                }
            }
        }
        double sum = pow(6,n);
        // n 到 6*n 个
        vector<double>ans(5*n+1);
        int i=0;
        for(int j=n;j<=6*n;j++){
            ans[i++] = dp[n][j] / sum;
        }

        return ans;
    }
};

0 赞同 0 条回复

哈哈哈哈开开心心普通 2023年7月23日上午4:28

class Solution:
    def dicesProbability(self, n: int) -> List[float]:
        dp = [[0] * (6 * n + 1) for _ in range(n + 1)]

        for i in range(6):
            dp[1][i + 1] = 1

        for i in range(2, n + 1):
            for j in range(i, 6 * n + 1):
                for k in range(1, 7):
                    if j < k:
                        break

                    dp[i][j] += dp[i - 1][j - k]

        res = [0] * (5 * n + 1)
        idx = 0
        den = pow(6, n)

        for i in range(n, 6 * n + 1):
            res[idx] = dp[n][i] / den
            idx += 1

        return res

记得查idx

0 赞同 0 条回复

mpweixin用户永久会员 2023年7月23日上午12:11

class Solution {
    public double[] dicesProbability(int n) {
       int[][] dp = new int[n + 1][6*n + 1];//n个骰子，投出m点的个数。

       for(int i = 1;i <= 6;i++){
           //一个骰子，组合出1-6点数的次数为1
           dp[1][i] = 1;
       }

       for(int i = 2;i <= n;i++){
           //n个骰子
           for(int j = i;j <= 6*i;j++){
               //可能出现的点数为n-6*n
               for(int k = 1;k <= 6;k++){
                   //当前n个骰子投出j点的可能
                   if(j < k){
                       break;
                   }
                   dp[i][j] += dp[i - 1][j - k];

               }
           }
       }

       double sum = Math.pow(6,n);  //  总共组合数
       double[] result = new double[5 * n + 1];
       for(int i = 0;i < result.length;i++){
           result[i] = dp[n][n + i] / sum;
       }

       return result;
    }
}

0 赞同 0 条回复

Ming 普通 2023年7月22日下午5:39

假设 dp[i][j] 表示投掷 i 个骰子后，点数和为 j 的次数。那么 dp[i][j] 可以由前一个状态 dp[i-1][j-k] 转移过来，其中 k 为第 i 个骰子的点数（1 到 6）。

public double[] dicesProbability(int n) {
        //  dp[i][j] 表示投掷 i 个骰子后，点数和为 j 的次数。
        // 那么 dp[i][j] 可以由前一个状态 dp[i-1][j-k] 转移过来，其中 k 为第 i 个骰子的点数（1 到 6）。
        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 <= i*6; 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 条回复

BOZ 普通 2023年7月22日下午2:49

【思路】DP思路，dp[i][j]表示用i个骰子掷出j总和的可能性有几种，最后将dp[n][n]~dp[n][6n]除以6^n即为答案
【复杂度】时间O(n^2)，空间可以优化为O(n)

class Solution {
public:
    vector<double> dicesProbability(int n) {
        int m = n * 6;
        int *dp = new int[m + 1];
        int *prev = new int[m + 1];
        for (int j = 0; j < m + 1; j++) dp[j] = (j && j <= 6);

        for (int i = 1; i < n; i++) {
            std::swap(dp, prev);
            dp[0] = 0;
            for (int j = 1; j < m + 1; j++) {
                dp[j] = 0;
                for (int k = max(j - 6, 0); k < j; k++)
                    dp[j] += prev[k];
            }
        }
        vector<double> result(n * 6 - n + 1);
        int total = pow(6, n);
        for (int j = n; j <= n * 6; j++) result[j - n] = (double)dp[j] / total;
        return result;
    }
};

0 赞同 0 条回复

Vow the vow。普通 2023年7月22日上午11:19

看大神的

public double[] dicesProbability(int n) {
        double[] dp = new double[6];
        Arrays.fill(dp,1.0/6); 
        for(int i = 2; i <= n; i++){
            double[] temp = new double[5 * i + 1];
            for(int j = 0; j < dp.length; j++){
                for(int k = 0; k < 6; k++){
                    temp[j+k] += dp[j]/6.0;
                }
            }
            dp= temp;
        }
        return dp;
    }

0 赞同 0 条回复

yxy 普通 2023年7月21日下午9:00

复杂度O(n^2)

class Solution {
public:
    vector<double> dicesProbability(int n) {
        vector<vector<double>> dp(n+1, vector<double>(6*n+1, 0));
        for(int i=1;i<=n;i++) // 枚举骰子数[1, n]
        {
            for(int j=i;j<=6*i;j++) // 枚举i枚骰子总和[i, 6*i]
            {
                if(i==1)
                    dp[i][j] = 1/6.0;
                for(int k=1;k<=6&&j-k>0;k++) // 枚举第i枚骰子出现的数字[1, 6]
                    dp[i][j]+=dp[i-1][j-k]*1/6.0;
            }
        }
        vector<double> res;
        for(int i=n;i<=6*n;i++)
            res.push_back(dp[n][i]);
        return res;
    }
};

0 赞同 0 条回复

花老爷普通 2023年7月21日下午5:00

动态规划，看其他人的
时间：O(n^2)
空间：O(n)

class Solution {
    public double[] dicesProbability(int n) {
        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年7月21日下午3:32

“`C++
vector probability(int n) {
// 定义一个n+1行、6n+1列的二维数组，用于记录每个点数和出现的次数
vector> dp(n+1, vector(6*n+1, 0));

// 初始化只有一个骰子的情况
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 <= j; k++) {
            dp[i][j] += dp[i-1][j-k];
        }
    }
}

// 计算概率分布
double total = pow(6, n); // 所有可能的情况总数
vector<double> result;
for (int i = n; i <= 6*n; i++) {
    result.push_back(dp[n][i] / total);
}

return result;

}

“`

0 赞同 0 条回复

Yodl. 普通 2023年7月21日下午3:12

//时间复杂度O(n²)，空间复杂度O(n)
class Solution {
public:
    vector<double> dicesProbability(int n) {
        vector<double> dp(6, 1.0 / 6.0);
        for (int i = 2; i <= n; i++) {
            vector<double> tmp(5 * i + 1, 0);
            for (int j = 0; j < dp.size(); j++) {
                for (int k = 0; k < 6; k++) {
                    tmp[j + k] += dp[j] / 6.0;
                }
            }
            dp = tmp;
        }
        return dp;
    }
};

0 赞同 0 条回复

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

共以下 13 个回答

MY

# 回答此问题取消回复

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

共以下 13 个回答

MY

# 回答此问题 取消回复

# 回答此问题取消回复