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

共以下 1 个回答

• 塔底的仰望 永久会员 2023年9月14日 下午11:50

  空间复制度O(n); 时间复杂度O(n)

  class Solution {
      public double[] dicesProbability(int n) {
          int[] dp = new int[6 * n + 1];
          int[] tmp = new int[6 * n + 1];
          for (int i = 1; i <= 6; i++) {
              dp[i] = 1;
              tmp[i] = 1;
          }
  
          for (int i = 2; i <= n; i++) {
              Arrays.fill(dp, 0);
              for (int j = i; j <= 6 * i; j++) {
                  for (int k = 1; k <= 6; k++) {
                      if (j - k < 0) {
                          break;
                      }
                      dp[j] += tmp[j - k];
                  }
              }
              int[] swap = dp;
              dp = tmp;
              tmp = swap;
          }
  
  
          double[] res = new double[5 * n + 1];
          int index = 0;
          double sum = Math.pow(6, n);
  
          for (int i = n; i <= 6 * n; i++) {
              //tmp里才保存着最终结果
              res[index++] = tmp[i] / sum;
          }
  
          return res;
      }
  }
  

  0 赞同 0 条回复

  登录以回复