1155. 掷骰子等于目标和的方法数

• 标签：动态规划
• 难度：中等

题目链接

• 1155. 掷骰子等于目标和的方法数 - 力扣

题目大意

描述：有 $n$ 个一样的骰子，每个骰子上都有 $k$ 个面，分别标号为 $1 \sim k$。现在给定三个整数 $n$、$k$ 和 $target$，滚动 $n$ 个骰子。

要求：计算出使所有骰子正面朝上的数字和等于 $target$ 的方案数量。

说明：

• $1 \le n, k \le 30$。
• $1 \le target \le 1000$。

示例：

• 示例 1：

输入：n = 1, k = 6, target = 3
输出：1
解释：你扔一个有 6 个面的骰子。
得到 3 的和只有一种方法。

• 示例 2：

输入：n = 2, k = 6, target = 7
输出：6
解释：你扔两个骰子，每个骰子有 6 个面。
得到 7 的和有 6 种方法 1+6 2+5 3+4 4+3 5+2 6+1。

解题思路

思路 1：动态规划

我们可以将这道题转换为「分组背包问题」中求方案总数的问题。将每个骰子看做是一组物品，骰子每一个面上的数值当做是每组物品中的一个物品。这样问题就转换为：用 $n$ 个骰子（$n$ 组物品）进行投掷，投掷出总和（总价值）为 $target$ 的方案数。

1. 划分阶段

按照总价值 $target$ 进行阶段划分。

2. 定义状态

定义状态 $dp[w]$ 表示为：用 $n$ 个骰子（$n$ 组物品）进行投掷，投掷出总和（总价值）为 $w$ 的方案数。

3. 状态转移方程

用 $n$ 个骰子（$n$ 组物品）进行投掷，投掷出总和（总价值）为 $w$ 的方案数，等于用 $n$ 个骰子（$n$ 组物品）进行投掷，投掷出总和（总价值）为 $w - d$ 的方案数累积值，其中 $d$ 为当前骰子掷出的价值，即：$dp[w] = dp[w] + dp[w - d]$。

4. 初始条件

• 用 $n$ 个骰子（$n$ 组物品）进行投掷，投掷出总和（总价值）为 $0$ 的方案数为 $1$。

5. 最终结果

根据我们之前定义的状态， $dp[w]$ 表示为：用 $n$ 个骰子（$n$ 组物品）进行投掷，投掷出总和（总价值）为 $w$ 的方案数。则最终结果为 $dp[target]$。

思路 1：代码

class Solution:
    def numRollsToTarget(self, n: int, k: int, target: int) -> int:
        dp = [0 for _ in range(target + 1)]
        dp[0] = 1
        MOD = 10 ** 9 + 7

        # 枚举前 i 组物品
        for i in range(1, n + 1):
            # 逆序枚举背包装载重量
            for w in range(target, -1, -1):
                dp[w] = 0
                # 枚举第 i - 1 组物品能取个数
                for d in range(1, k + 1):
                    if w >= d:
                        dp[w] = (dp[w] + dp[w - d]) % MOD
                        
        return dp[target] % MOD

思路 1：复杂度分析

• 时间复杂度：$O(n \times m \times target)$。
• 空间复杂度：$O(target)$。