题目

https://leetcode-cn.com/problems/nge-tou-zi-de-dian-shu-lcof/

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

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

示例 1:

输入: 1

输出: [0.16667,0.16667,0.16667,0.16667,0.16667,0.16667]

示例 2:

输入: 2

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

限制：

1 <= n <= 11

代码和思路

https://leetcode-cn.com/problems/nge-tou-zi-de-dian-shu-lcof/solution/nge-tou-zi-de-dian-shu-dong-tai-gui-hua-ji-qi-yo-3/

动态规划

动态规划

  1. class Solution:
  2.     def twoSum(self, n: int) -> List[float]:
  3.         dp = [[0 for i in range(n*6+1)] for j in range(n+1)]
  4.         for i in range(1,7):
  5.             dp[1][i] = 1
  6.         for i in range(2, n+1):
  7.             for j in range(i, 6*n+1):
  8.                 for k in range(1, 7):
  9.                     if j - k <= 0:
  10.                         break
  11.                     dp[i][j] += dp[i-1][j-k]
  12.         total = 6**n
  13.         return [i/total for i in dp[n][n:6*n+1]]

动态规划优化内存空间

  1. class Solution:
  2.     def twoSum(self, n: int) -> List[float]:
  3.         dp = [0 for i in range(n*6+1)]
  4.         for i in range(1,7):
  5.             dp[i] = 1
  6.         for i in range(2, n+1):
  7.             for j in range(6*i, i-1, -1):
  8.                 dp[j] = 0
  9.                 for k in range(1, 7):
  10.                     if j - k < i-1:
  11.                         break
  12.                     dp[j] += dp[j-k]
  13.         total = 6**n
  14.         return [i/total for i in dp[n:6*n+1]]