LeetCode 1155中等DP
掷骰子的 N 种方法 图解题解
这道题到底在问什么
给定骰子数量 n、每个骰子的面数 k(点数 1 到 k)、目标总和 target。求所有骰子点数之和恰好为 target 的方案数,对 1e9+7 取模。每个骰子有序、互相独立。
- 输入
- n = 1, k = 6, target = 3
- 输出
- 1(只有掷出 3 这一种)
- 输入
- n = 2, k = 6, target = 7
- 输出
- 6(1+6、2+5、3+4、4+3、5+2、6+1)
- 输入
- n = 30, k = 30, target = 500
- 输出
- 222616187(方案极多,取模后的结果)
最优解：一步一步想明白
- 3一句话套路:每加一个骰子,就把它能掷出的 1 到 k 点,分别从上一行对应的格子累加过来。下面逐格填表套这条规则。
- 4先看这张表的骨架:列头是点数总和 0 到 7,行头是「用了几个骰子」0 到 2。dp[i][s] 就是「用前 i 个骰子掷出总和 s」的方案数,现在全是「·」表示还没算。
- 5基准行 = 一个骰子都不掷。这时总和只能是 0,而且「什么都不掷」算作 1 种方案,所以 dp[0][0]=1(紫格)。
- 6还是 0 个骰子:想凑出和 1 是不可能的(没有骰子怎么也凑不出正数和),dp[0][1]=0(紫格)。基准行除了 dp[0][0] 全是 0。
- 7还是 0 个骰子:想凑出和 2 是不可能的(没有骰子怎么也凑不出正数和),dp[0][2]=0(紫格)。基准行除了 dp[0][0] 全是 0。
- 8还是 0 个骰子:想凑出和 3 是不可能的(没有骰子怎么也凑不出正数和),dp[0][3]=0(紫格)。基准行除了 dp[0][0] 全是 0。
- 9还是 0 个骰子:想凑出和 4 是不可能的(没有骰子怎么也凑不出正数和),dp[0][4]=0(紫格)。基准行除了 dp[0][0] 全是 0。
- 10还是 0 个骰子:想凑出和 5 是不可能的(没有骰子怎么也凑不出正数和),dp[0][5]=0(紫格)。基准行除了 dp[0][0] 全是 0。
- 11还是 0 个骰子:想凑出和 6 是不可能的(没有骰子怎么也凑不出正数和),dp[0][6]=0(紫格)。基准行除了 dp[0][0] 全是 0。
- 12还是 0 个骰子:想凑出和 7 是不可能的(没有骰子怎么也凑不出正数和),dp[0][7]=0(紫格)。基准行除了 dp[0][0] 全是 0。
- 13用了 1 个骰子还想让总和为 0?不可能,每个骰子至少掷 1 点。dp[1][0]=0(紫格)。
- 14算 dp[1][1]:第 1 个骰子掷 face(1 到 6),要凑和 1,前 0 个骰子就得凑出 1-face。把上一行所有 1-face ≥ 0 的格子(蓝格)挑出来,准备相加。
- 15把这些蓝格的值加起来取模:1 = 1。填入紫格 dp[1][1]=1。
- 16算 dp[1][2]:第 1 个骰子掷 face(1 到 6),要凑和 2,前 0 个骰子就得凑出 2-face。把上一行所有 2-face ≥ 0 的格子(蓝格)挑出来,准备相加。
- 17把这些蓝格的值加起来取模:0 + 1 = 1。填入紫格 dp[1][2]=1。
- 18算 dp[1][3]:第 1 个骰子掷 face(1 到 6),要凑和 3,前 0 个骰子就得凑出 3-face。把上一行所有 3-face ≥ 0 的格子(蓝格)挑出来,准备相加。
- 19把这些蓝格的值加起来取模:0 + 0 + 1 = 1。填入紫格 dp[1][3]=1。
- 20算 dp[1][4]:第 1 个骰子掷 face(1 到 6),要凑和 4,前 0 个骰子就得凑出 4-face。把上一行所有 4-face ≥ 0 的格子(蓝格)挑出来,准备相加。
- 21把这些蓝格的值加起来取模:0 + 0 + 0 + 1 = 1。填入紫格 dp[1][4]=1。
- 22算 dp[1][5]:第 1 个骰子掷 face(1 到 6),要凑和 5,前 0 个骰子就得凑出 5-face。把上一行所有 5-face ≥ 0 的格子(蓝格)挑出来,准备相加。
- 23把这些蓝格的值加起来取模:0 + 0 + 0 + 0 + 1 = 1。填入紫格 dp[1][5]=1。
- 24算 dp[1][6]:第 1 个骰子掷 face(1 到 6),要凑和 6,前 0 个骰子就得凑出 6-face。把上一行所有 6-face ≥ 0 的格子(蓝格)挑出来,准备相加。
- 25把这些蓝格的值加起来取模:0 + 0 + 0 + 0 + 0 + 1 = 1。填入紫格 dp[1][6]=1。
- 26算 dp[1][7]:第 1 个骰子掷 face(1 到 6),要凑和 7,前 0 个骰子就得凑出 7-face。把上一行所有 7-face ≥ 0 的格子(蓝格)挑出来,准备相加。
- 27把这些蓝格的值加起来取模:0 + 0 + 0 + 0 + 0 + 0 = 0。填入紫格 dp[1][7]=0。
- 28用了 2 个骰子还想让总和为 0?不可能,每个骰子至少掷 1 点。dp[2][0]=0(紫格)。
- 29算 dp[2][1]:第 2 个骰子掷 face(1 到 6),要凑和 1,前 1 个骰子就得凑出 1-face。把上一行所有 1-face ≥ 0 的格子(蓝格)挑出来,准备相加。
- 30把这些蓝格的值加起来取模:0 = 0。填入紫格 dp[2][1]=0。
- 31算 dp[2][2]:第 2 个骰子掷 face(1 到 6),要凑和 2,前 1 个骰子就得凑出 2-face。把上一行所有 2-face ≥ 0 的格子(蓝格)挑出来,准备相加。
- 32把这些蓝格的值加起来取模:1 + 0 = 1。填入紫格 dp[2][2]=1。
- 33算 dp[2][3]:第 2 个骰子掷 face(1 到 6),要凑和 3,前 1 个骰子就得凑出 3-face。把上一行所有 3-face ≥ 0 的格子(蓝格)挑出来,准备相加。
- 34把这些蓝格的值加起来取模:1 + 1 + 0 = 2。填入紫格 dp[2][3]=2。
- 35算 dp[2][4]:第 2 个骰子掷 face(1 到 6),要凑和 4,前 1 个骰子就得凑出 4-face。把上一行所有 4-face ≥ 0 的格子(蓝格)挑出来,准备相加。
- 36把这些蓝格的值加起来取模:1 + 1 + 1 + 0 = 3。填入紫格 dp[2][4]=3。
- 37算 dp[2][5]:第 2 个骰子掷 face(1 到 6),要凑和 5,前 1 个骰子就得凑出 5-face。把上一行所有 5-face ≥ 0 的格子(蓝格)挑出来,准备相加。
- 38把这些蓝格的值加起来取模:1 + 1 + 1 + 1 + 0 = 4。填入紫格 dp[2][5]=4。
- 39算 dp[2][6]:第 2 个骰子掷 face(1 到 6),要凑和 6,前 1 个骰子就得凑出 6-face。把上一行所有 6-face ≥ 0 的格子(蓝格)挑出来,准备相加。
- 40把这些蓝格的值加起来取模:1 + 1 + 1 + 1 + 1 + 0 = 5。填入紫格 dp[2][6]=5。
- 41算 dp[2][7]:第 2 个骰子掷 face(1 到 6),要凑和 7,前 1 个骰子就得凑出 7-face。把上一行所有 7-face ≥ 0 的格子(蓝格)挑出来,准备相加。
- 42把这些蓝格的值加起来取模:1 + 1 + 1 + 1 + 1 + 1 = 6。填入紫格 dp[2][7]=6。
- 43整张表填满,右下角 dp[2][7] = 6 就是答案:用 2 个六面骰子掷出总和 7 的方案数。回头数一数:1+6、2+5、3+4、4+3、5+2、6+1,正好 6 种。
- 44复盘整条思路:dp[i][s] 表示「前 i 个骰子凑出和 s 的方案数」,每多一个骰子就把它的 1 到 k 点从上一行累加过来,逐行往下推,右下角即答案 6。
⚠️ 容易写错的地方
✗ 错：忘记取模,中间结果溢出
✓ 对：每次累加后立刻对 1e9+7 取模
n=30、k=30、target=500 时方案数极大,不取模会整型溢出得到错误甚至负数
✗ 错：dp[0] 初始化成 0
✓ 对：dp[0]=1,代表「凑和 0 有 1 种空方案」
它是所有转移的种子,设成 0 会让整张表全是 0
✗ 错：漏判越界或在同一行原地更新
✓ 对：枚举点数时只累加合法项,并写进新数组 ndp
负下标会取到错误格子;边读边写会把本轮新值当上一行重复累加,结果偏大
完整代码（Python / C++ / Java）
Python
class Solution:
def numRollsToTarget(self, n: int, k: int, target: int) -> int:
MOD = 10**9 + 7
dp = [0] * (target + 1)
dp[0] = 1
for _ in range(n):
ndp = [0] * (target + 1)
for s, v in enumerate(dp):
if v:
for face in range(1, k + 1):
if s + face <= target:
ndp[s + face] = (ndp[s + face] + v) % MOD
dp = ndp
return dp[target]C++
#include <vector>
using namespace std;
class Solution {
public:
int numRollsToTarget(int n, int k, int target) {
const int MOD = 1000000007;
vector<int> dp(target + 1);
dp[0] = 1;
for (int i = 0; i < n; ++i) {
vector<int> ndp(target + 1);
for (int s = 0; s <= target; ++s) if (dp[s]) {
for (int f = 1; f <= k && s + f <= target; ++f) ndp[s+f] = (ndp[s+f] + dp[s]) % MOD;
}
dp.swap(ndp);
}
return dp[target];
}
};Java
import java.util.*;
class Solution {
public int numRollsToTarget(int n, int k, int target) {
int MOD = 1_000_000_007;
int[] dp = new int[target + 1];
dp[0] = 1;
for (int i = 0; i < n; i++) {
int[] ndp = new int[target + 1];
for (int s = 0; s <= target; s++) if (dp[s] != 0) {
for (int f = 1; f <= k && s + f <= target; f++) ndp[s + f] = (ndp[s + f] + dp[s]) % MOD;
}
dp = ndp;
}
return dp[target];
}
}复杂度
时间
O(n·k·target)
n 个骰子,每个骰子枚举每个和 s(共 target 个)再枚举 k 种点数
空间
O(target)
滚动数组只存一行;若用完整二维表则是 O(n·target)
看不够？换成动画再走一遍
上面的推演每一步都对应一帧动画。点开交互动画版，能一步步看着 掷骰子的 N 种方法 的数据怎么变、指针怎么走，还能切 Python / Java / C++ 跟着练。
面试官可能追问
这题和「完全背包 / 零钱兑换 II」有什么联系?+
骨架几乎一样,都是分组累加的计数 DP。区别在于:本题每个骰子只能贡献一个点数(1 到 k),且骰子是有顺序、有数量限制的(恰好 n 个),所以外层固定循环 n 次、内层枚举 k 种点数;零钱兑换 II 是物品可无限取、不限个数。本题更像「恰好用 n 个分组、每组选一个值」的分组背包计数。
如果改成求「点数和小于等于 target」的方案数怎么办?+
在填完表后,把最后一行 dp[n][0] 到 dp[n][target] 全部加起来即可;或者在转移里维护一个前缀和数组,转移时直接区间求和把内层枚举 k 的复杂度降到 O(1),整体从 O(n·k·target) 优化到 O(n·target)。
想听吴师兄把这道题讲给你听？
文字版和动画都随便看。开通图解算法年卡，可以听吴师兄声线把 掷骰子的 N 种方法 一步步讲透（全站 0 节语音精讲，持续扩充）， 卡住的地方还有 AI 私教小欧就着动画帮你拆到懂。
本平台为独立第三方培训机构，与华为技术有限公司无任何关联；课程的服务内容与权益以购买协议为准，学习效果因个人情况而异。「华为 OD」「华为可信」等仅为对岗位与考试方向的客观描述，相关商标归各自权利人所有。