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

共以下 5 个回答

• Kisara 普通 2024年12月31日 上午9:02

  dp解法

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

  0 赞同 0 条回复

  登录以回复
• 陆狗陆狗 普通 2024年12月30日 下午11:36

  解题思路
  – dp[n][j] ，n表示是第几个骰子。j表示总点数。这个题目允许存在空间浪费。n肯定比n-1的j的范围要大。比如dp[1]的j的范围是1~6，dp[2]的j的范围是2~12
  – dp[n][j] 和dp[n-1][n-1的j]的关系？j的构成要考虑dp[n]点数是1,2,3,4,5,6时和dp[n-1]不同j的组合。
  【题解1】

  class Solution {
      public double[] statisticsProbability(int num) {
          // dp[n][j] ，n表示是第几个骰子。j表示总点数。这个题目允许存在空间浪费。n肯定比n-1的j的范围要大
         //  dp[n][j] 和dp[n-1][j前面]的关系？j的构成要考虑dp[n]点数是1,2,3,4,5,6时和dp[n-1]的组合
          // 这里长度为什么是+1，是为了写代码理解
          double[][] dp = new double[num + 1][num * 6 + 1];
          // 初始化
          for (int j = 1; j <= 6; j++) {
              dp[1][j] = 1.0 / 6;
          }
          // 骰子个数的循环
          for (int n = 2; n <= num; n++) {
              // 点数的循环
              for (int j = n; j <= n * 6; j++) {
                  // 当前骰子的点数
                  for (int k = 1; k <= 6; k++) {
                      // 比如当前总点数是2，当前骰子的点数是1，那么上一个的点数是1的有效
                      // 比如当前总点数是3，当前骰子的点数是1，那么上一个的点数是1,2的有效
                      // 总点数-当前点数=上一个骰子的点数和>=上一个dp的最小点数
                      if (j - k >= n - 1) {
                          dp[n][j] = dp[n][j] + dp[n - 1][j - k] * (1.0 / 6);
                      }
                  }
              }
          }
  
          // 目标的数组
          // 目标数组里面骰子总点数的范围 （num~num*6）,因而个数是num * 6 - num + 1=5*num+1
          double[] result = new double[num * 5 + 1];
          for (int j = num; j <= num * 6; j++) {
              // 下标从0开始
              result[j - num] = dp[num][j];
          }
          return result;
  
      }
  }
  

  0 赞同 0 条回复

  登录以回复
• Pendulumpal 普通 2024年12月25日 下午9:26

  时间复杂度：O(n ^2)
  f(n,x)=i=1∑6f(n−1,x−i)×1/6

  class Solution {
  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;
      }
  }
  
  

  0 赞同 0 条回复

  登录以回复
• Aatorx 永久会员 2024年12月24日 下午3:20

  class Solution {
  public:
      vector<double> statisticsProbability(int num) {
          vector<double> dp(6, 1.0/6.0);
          for(int i = 2; i <= num; i++) {
              vector<double> temp(i * 5 + 1, 0.0);
              for(int j = 0; j < dp.size(); j++) {
                  for(int k = 0; k < 6; k++) {
                      temp[k + j] += dp[j] / 6.0;
                  }
              }
              dp = temp;
          }
          return dp;
      }
  };
  

  时间复杂度O(N^2)，空间复杂度O(N)。

  0 赞同 0 条回复

  登录以回复
• 月下足迹 普通 2024年12月24日 上午9:59

  //n个骰子的结果需要用到n-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] / 6.0;
  }
  }
  dp = tmp;
  }
  return dp;

  0 赞同 0 条回复

  登录以回复