What pattern does Number of Dice Rolls With Target Sum follow?

It follows a state transition dynamic programming pattern where states track remaining dice and current sum.

Can this problem be solved with recursion alone?

Recursion without memoization is inefficient and may exceed time limits; memoized DP or iterative DP is recommended.

Why do we use modulo 10^9 + 7 in this problem?

Because the total number of sequences grows exponentially, modulo prevents integer overflow and keeps results within limits.

How can space complexity be optimized?

Use a rolling array to store only the current and previous dice states, reducing space from O(n * target) to O(target).

Is it necessary to iterate over all face values for each dice?

Yes, iterating over 1 to k for each dice ensures all valid sequences are counted according to state transition DP.

#1155

Medium

auto_awesome状态·转移·动态规划

LeetCode 题解工作台

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

这里有 n 个一样的骰子，每个骰子上都有 k 个面，分别标号为 1 到 k 。给定三个整数 n 、 k 和 target ，请返回投掷骰子的所有可能得到的结果（共有 k n 种方式），使得骰子面朝上的数字总和等于 target 。由于答案可能很大，你需要对 10 9 + 7 取模。示例 1：…

动态规划

题目描述

这里有 n 个一样的骰子，每个骰子上都有 k 个面，分别标号为 1 到 k 。

给定三个整数 n、k 和 target，请返回投掷骰子的所有可能得到的结果（共有 kⁿ 种方式），使得骰子面朝上的数字总和等于 target。

由于答案可能很大，你需要对 10⁹ + 7 取模。

示例 1：

输入：n = 1, k = 6, target = 3
输出：1
解释：你掷了一个有 6 个面的骰子。
得到总和为 3 的结果的方式只有一种。

示例 2：

输入：n = 2, k = 6, target = 7
输出：6
解释：你掷了两个骰子，每个骰子有 6 个面。
有 6 种方式得到总和为 7 的结果: 1+6, 2+5, 3+4, 4+3, 5+2, 6+1。

示例 3：

输入：n = 30, k = 30, target = 500
输出：222616187
解释：返回的结果必须对 10⁹ + 7 取模。

提示：

1 <= n, k <= 30
1 <= target <= 1000

lightbulb

解题思路

方法一：动态规划

我们定义 $f[i][j]$ 表示使用 $i$ 个骰子，和为 $j$ 的方案数。那么我们可以得到状态转移方程：

f[i][j] = \sum_{h=1}^{\min(j, k)} f[i-1][j-h]

其中 $h$ 表示第 $i$ 个骰子的点数。

初始时 $f[0][0] = 1$ ，最终的答案即为 $f[n][target]$ 。

时间复杂度 $O(n \times k \times target)$ ，空间复杂度 $O(n \times target)$ 。

我们注意到，状态 $f[i][j]$ 只和 $f[i-1][]$ 有关，因此我们可以使用滚动数组的方式，将空间复杂度优化到 $O(target)$ 。

1

2

3

4

5

6

7

8

9

10

11

class Solution:
    def numRollsToTarget(self, n: int, k: int, target: int) -> int:
        f = [[0] * (target + 1) for _ in range(n + 1)]
        f[0][0] = 1
        mod = 10**9 + 7
        for i in range(1, n + 1):
            for j in range(1, min(i * k, target) + 1):
                for h in range(1, min(j, k) + 1):
                    f[i][j] = (f[i][j] + f[i - 1][j - h]) % mod
        return f[n][target]

speed

复杂度分析

指标	值
时间	complexity is O(n * target * k) because for each of n dice and each intermediate sum up to target, we iterate over k faces. Space complexity is O(n * target) for the DP table, which can be optimized to O(target) using rolling arrays.
空间	Depends on the final approach

psychology

面试官常问的追问

外企场景

question_mark
The candidate should recognize the state definition as remaining dice and current sum.
question_mark
The interviewer may check whether the solution handles large numbers with modulo 10^9 + 7.
question_mark
Expect discussion of DP optimization to reduce space using a rolling array for sums.

warning

常见陷阱

外企场景

error
Forgetting to apply modulo at each update, causing integer overflow.
error
Incorrectly defining the DP state or transitions, leading to overcounting or missed sequences.
error
Attempting brute-force recursion without memoization, which exceeds time limits.

swap_horiz

进阶变体

外企场景

arrow_right_alt
Count sequences where dice have non-uniform faces or different ranges.
arrow_right_alt
Find the probability of rolling a sum rather than counting sequences.
arrow_right_alt
Determine the minimum number of dice needed to reach at least the target sum.

help

常见问题

外企场景

继续练习

#1162 地图分析 #1147 段式回文 #1143 最长公共子序列