第 60 题：
个骰子的点数（典型动态规划问题）
传送门：AcWing：骰子的点数。
将一个骰子投掷
，
。
掷出某一点数，可能有多种掷法，例如投掷
次，掷出
点，共有
，
两种掷法。
请求出投掷
样例1：
输入：
n=1输出：
[1, 1, 1, 1, 1, 1]解释：投掷 1 次，可能出现的点数为 1-6 ，共计 6 种。每种点数都只有 1 种掷法。所以输出
[1, 1, 1, 1, 1, 1]。样例2：
输入：n=2
输出：
[1, 2, 3, 4, 5, 6, 5, 4, 3, 2, 1]解释：投掷 2 次，可能出现的点数为 2-12，共计 11 种。每种点数可能掷法数目分别为
1,2,3,4,5,6,5,4,3,2,1。所以输出[1, 2, 3, 4, 5, 6, 5, 4, 3, 2, 1]。
思路：典型动态规划问题。定义状态 dp[i][j] 表示用 i 个骰子扔出和为 j 的可能数，因为第 i 个骰子可能扔出 1-6 的点数。根据此写出状态转移方程：
由于我们只需要用到最后一次的结果，因此为了节省空间可以使用滚动数组，将二维 dp 数组变为一维。
时间复杂度分析：。
Python 代码：
class Solution(object):
def numberOfDice(self, n):
"""
:type n: int
:rtype: List[int]
"""
dp = [0 for _ in range(6 * n + 1)]
# 动归数组初始值，表示 1 个骰子扔出 1-6 的可能数都为 1
for i in range(1, 7):
dp[i] = 1
# 表示仍第 2 个骰子到第 n 个骰子
for i in range(2, n + 1):
# 从后向前写
for j in range(6 * i, -1, -1):
dp[j] = 0
# 最后一个骰子可以扔 1 - 6 点
for k in range(6, 0, -1):
if j - k < 0:
continue
dp[j] += dp[j - k]
# 扔 n 个骰子的和为 [n, 6 * n]
return dp[n:]
作者：cornerCao
链接：https://www.acwing.com/solution/acwing/content/852/
来源：AcWing
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。
