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

共以下 6 个回答

• 方铎码农 普通 2024年4月8日 下午4:32

  class Solution {
      public double[] statisticsProbability(int num) {
          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]/6.0;
                  }
              }
              dp = tmp;
          }
          return dp;
      }
  }
  

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

  0 赞同 0 条回复

  登录以回复
• 王位詮釋 普通 2024年4月7日 下午8:30

  class Solution {
      public double[] statisticsProbability(int num) {
          //dp[i][j]表示当有i个骰子且掷出来的点数和为j的时候的次数
          int[][] dp = new int[num+1][6*num+1];
  
          //初始化
          for(int i=1;i<=6;i++){
              dp[1][i] = 1;//只有一个骰子的时候只能掷出来1-6;
          }
  
          //根据状态转移方程计算
          for(int i=2;i<=num;i++){//一共有num个骰子
  
              for(int j=i;j<=6*i;j++){//当有i个骰子的时候,取值范围是：i-6i j表示掷出来的点数和
  
                  for(int k=1;k<=6;k++){//状态转移方程 k表示第i次掷出来的点数k取值为1-6
  
                      if(j<k){//j表示点数的和,所以j可能会小于k 这时候是不应该计算的
                      //比如说2个骰子,如果点数是2的话 要么第一次就掷出来2 要么第一次1第二次也是1
                      //一旦第二次掷出来3以上 (即j<k的情况) 就不可能会有2了 所以3以后的情况是不能计算的
                          break;
                      }
                      dp[i][j]+=dp[i-1][j-k];
                  }
              }
          }
          double[] res = new double[5*num+1];
          int index = 0;
          double sum = Math.pow(6,num);
          for(int i=num;i<=6*num;i++){
              res[index++] = dp[num][i]/sum;
          }
          return res;
      }
  }
  思路：二维数组dp[i][j]代表投掷i个骰子时点数和为j的次数，这样在投掷的时候就可以通过dp[i-1][j-1...j-6]来算出dp[i][j]了，最后一共是5*num+1中点数和，且一共是6^num种组合，所以可以通过这样来计算最终结果。
  时间复杂度：O(n2)
  空间复杂度：O(n2)
  

  0 赞同 0 条回复

  登录以回复
• 云无深雁影 普通 2024年4月4日 下午11:25

  class Solution {
  public double[] statisticsProbability(int num) {
  double[][] dp = new double[num + 1][num * 6 + 1];
  for(int i = 1; i <= 6; i++)
  dp[1][i] = 1.0 / 6;

      for(int i = 2; i <= num; i++){
          for(int j = i; j <= num*6; j++){
              for(int k = 1; k <= 6; k++){
                  if((j - k) >= (i - 1))
                      dp[i][j] += dp[i-1][j - k] / 6;
              }
          }
      }
      double[] ans = new double[5*num+1];
      for(int i = 0; i < 5*num + 1; i++)
          ans[i] = dp[num][i + num];
      return ans;
  
  }
  

  }
  //时空复杂度均为On2

  0 赞同 0 条回复

  登录以回复
• Raphtalia. 普通 2024年4月4日 下午1:13

  class Solution {
  public:
  vector statisticsProbability(int n) {
  vector res (n * 6 – n + 1);
  vector<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 ++) {
  if(j – k > 0) {
  dp[i][j] += dp[i – 1][j – k];
  } else {
  break;
  }
  }
  }
  }

      double tmp = pow(6.0, n);//除数
  
      for(int i = n; i <= 6 * n; i ++) {
          res[i - n] = dp[n][i] / tmp;
      }
  
      return res;
  }
  

  };

  0 赞同 0 条回复

  登录以回复
• 紫芝 普通 2024年4月2日 下午11:41

  思路：假设骰子个数为 n 个，dp[n, x] 表示 n 个骰子点数和为 x 的概率，则当骰子个数为 n + 1 个时：
  dp[n+1, x] 为 n+1 个骰子点数和为 x 的概率，可以从 dp[n] 计算：
  dp[n+1, x] = dp[n, x-1] * 1/6 + dp[n, x-2] * 1/6 + … + dp[n, x-6] * 1/6
  可以发现，当 x < i 时，x-i 可能小于0， 发生越界，因此我们可以正序进行计算，即 dp[n, x] 仅可以为 dp[n+1, x+1], dp[n+1, x+2], …, dp[n+1, x+6] 增加概率:
  dp[n+1, x+1] += dp[n, x] * 1/6;
  dp[n+1, x+2] += dp[n, x] * 1/6;
  …
  dp[n+1, x+6] += dp[n, x] * 1/6

  “`c++
  class Solution {
  public:
  vector statisticsProbability(int num) {
  vector dp(6, 1.0 / 6.0);
  for (int i=2; i<=num; i++) { vector tmp(5 * i + 1, 0.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 条回复

  登录以回复
• heathhou 普通 2024年4月2日 下午11:10

  class Solution {
  public:
      vector<double> statisticsProbability(int num) {
          // dp[i][j]: 当有i个骰子的时候，投出的点数和为j的 可能数
          vector<vector<int>> dp(num+1, vector<int>(6*num+1));
  
          // 初始化
          for(int i = 1; i <= 6; ++i){
              dp[1][i] = 1;
          }
  
          for(int i =2; i <=num; ++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];
                  }
              }
          }
          // num ~ 6*num
          vector<double> res(5*num +1);
          int index = 0;
          // 总共的可能性的数量
          double sum = pow(6, num);
  
          for(int i = num; i <= 6*num; ++i){
              res[index++] = static_cast<double>(dp[num][i]) / sum;
          }
  
          return res;
  
  
  
  
      }
  };
  

  0 赞同 0 条回复

  登录以回复