《剑指 Offer （第 2 版）》第 60 题：n 个骰子的点数

第 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
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。