面试题 60. n 个骰子的点数

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

输入: 2
输出: [0.02778,0.05556,0.08333,0.11111,0.13889,0.16667,0.13889,0.11111,0.08333,0.05556,0.02778]

for (第n枚骰子的点数 i = 1; i <= 6; i ++) {
    dp[n][j] += dp[n-1][j - i]
}

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

class Solution:
    def twoSum(self, n: int) -> List[float]:
        dp = [[0 for _ in range(6 * n + 1)] for _ in range(n + 1)]
        for j in range(1, 7):
            dp[1][j] = 1
        for i in range(2, n + 1):
            for j in range(i, 6 * i + 1):
                for k in range(1, 7):
                    if j <= k:
                        break
                    dp[i][j] += dp[i - 1][j - k]
        res, total = [], pow(6, n)
        for i in range(5 * n + 1):
            res.append(dp[n][n + i] / total)
        return res

class Solution {
    public double[] twoSum(int n) {
        int[][] dp = new int[n + 1][6 * n + 1];
        for (int j = 1; j <= 6; ++j) {
            dp[1][j] = 1;
        }
        for (int i = 2; i <= n; ++i) {
            for (int j = i; j <= 6 * i; ++j) {
                for (int k = 1; k <= 6 && j > k; ++k) {
                    dp[i][j] += dp[i - 1][j - k];
                }
            }
        }
        double[] res = new double[5 * n + 1];
        double all = Math.pow(6, n);
        for (int i = 0; i <= 5 * n; ++i) {
            res[i] = dp[n][n + i] * 1.0 / all;
        }
        return res;
    }
}

/**
 * @param {number} n
 * @return {number[]}
 */
var twoSum = function (n) {
  function backtrack(sum, time) {
    if (time === n) {
      res[sum]++;
      return;
    }
    for (let i = 1; i <= 6; i++) {
      backtrack(sum + i, time + 1);
    }
  }
  let len = n * 6;
  let t = 6 ** n;
  let res = new Array(len + 1).fill(0);
  backtrack(0, 0);
  return res.slice(n).map((e) => e / t);
};