【剑指offer:n个骰子的点数】两种思路:递归+动态规划

题目描述:把 n 个骰子扔在地上,所有骰子朝上一面的点数之和为 s。输入 n,打印出 s 的所有可能的值出现的概率。

你需要用一个浮点数数组返回答案,其中第 i 个元素代表这 n 个骰子所能掷出的点数集合中第 i 小的那个的概率。

示例

输入: 1
输出: [0.16667,0.16667,0.16667,0.16667,0.16667,0.16667]

# 解法 1:递归穷举所有情况(TLE)

这题可以使用递归来穷举所有情况。过程中,借助哈希表来存放每种情况对应的数值出现的次数。

// ac地址:https://leetcode-cn.com/problems/nge-tou-zi-de-dian-shu-lcof/
// 原文地址:https://xxoo521.com/2020-03-29-two-sum/
/**
 * @param {number} n
 * @return {number[]}
 */
var twoSum = function (n) {
  const map = new Map();
  const totalTimes = Math.pow(6, n); // 出现的总次数
  inner(0, 1);

  const res = [];
  for (const times of map.values()) {
    res.push(times / totalTimes);
  }

  return res;

  /**
   * @param {number[]} total
   * @param {number} step
   */
  function inner(total, step) {
    if (step > n) {
      map.set(total, map.has(total) ? map.get(total) + 1 : 1);
      return;
    }

    for (let i = 1; i <= 6; ++i) {
      inner(total + i, step + 1);
    }
  }
};

这种方法由于递归会有重复计算的问题,时间复杂度高达$O(6^n)$。

题目要求 n 的大小范围是[1, 11],当 n=11 的时候,会 TLE。

# 解法 2: 动态规划

dp 数组的含义:dp[i][j] 代表 i 枚骰子朝上一面之和到达 j 的总个数。

状态转移方程是: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]

代码实现如下:

// ac地址:https://leetcode-cn.com/problems/nge-tou-zi-de-dian-shu-lcof/
// 原文地址:https://xxoo521.com/2020-03-29-two-sum/
/**
 * @param {number} n
 * @return {number[]}
 */
var twoSum = function (n) {
  const dp = new Array(n + 1);
  for (let i = 1; i <= n; ++i) {
    dp[i] = new Array(67).fill(0);
  }

  for (let j = 1; j <= 6; ++j) {
    dp[1][j] = 1;
  }

  // 骰子个数
  for (let i = 2; i <= n; ++i) {
    // i个骰子能够到达的最大值
    for (let j = i; j <= 6 * i; ++j) {
      // 状态转移
      for (let k = 1; j - k > 0 && k <= 6; ++k) {
        dp[i][j] += dp[i - 1][j - k];
      }
    }
  }

  let totalTimes = Math.pow(6, n);
  const ans = [];
  for (let j = n; j <= n * 6; ++j) {
    ans.push(dp[n][j] / totalTimes);
  }
  return ans;
};

# 更多资料

整理不易,若对您有帮助,请给个「关注+点赞」,您的支持是我更新的动力 👇