题目描述
思路解析动画文字版
一句话套路:每加一个骰子,就把它能掷出的 1 到 k 点,分别从上一行对应的格子累加过来。下面逐格填表套这条规则。
先看这张表的骨架:列头是点数总和 0 到 7,行头是「用了几个骰子」0 到 2。dp[i][s] 就是「用前 i 个骰子掷出总和 s」的方案数,现在全是「·」表示还没算。
基准行 = 一个骰子都不掷。这时总和只能是 0,而且「什么都不掷」算作 1 种方案,所以 dp[0][0]=1(紫格)。
还是 0 个骰子:想凑出和 1 是不可能的(没有骰子怎么也凑不出正数和),dp[0][1]=0(紫格)。基准行除了 dp[0][0] 全是 0。
还是 0 个骰子:想凑出和 2 是不可能的(没有骰子怎么也凑不出正数和),dp[0][2]=0(紫格)。基准行除了 dp[0][0] 全是 0。
还是 0 个骰子:想凑出和 3 是不可能的(没有骰子怎么也凑不出正数和),dp[0][3]=0(紫格)。基准行除了 dp[0][0] 全是 0。
还是 0 个骰子:想凑出和 4 是不可能的(没有骰子怎么也凑不出正数和),dp[0][4]=0(紫格)。基准行除了 dp[0][0] 全是 0。
还是 0 个骰子:想凑出和 5 是不可能的(没有骰子怎么也凑不出正数和),dp[0][5]=0(紫格)。基准行除了 dp[0][0] 全是 0。
还是 0 个骰子:想凑出和 6 是不可能的(没有骰子怎么也凑不出正数和),dp[0][6]=0(紫格)。基准行除了 dp[0][0] 全是 0。
还是 0 个骰子:想凑出和 7 是不可能的(没有骰子怎么也凑不出正数和),dp[0][7]=0(紫格)。基准行除了 dp[0][0] 全是 0。
用了 1 个骰子还想让总和为 0?不可能,每个骰子至少掷 1 点。dp[1][0]=0(紫格)。
算 dp[1][1]:第 1 个骰子掷 face(1 到 6),要凑和 1,前 0 个骰子就得凑出 1-face。把上一行所有 1-face ≥ 0 的格子(蓝格)挑出来,准备相加。
把这些蓝格的值加起来取模:1 = 1。填入紫格 dp[1][1]=1。
算 dp[1][2]:第 1 个骰子掷 face(1 到 6),要凑和 2,前 0 个骰子就得凑出 2-face。把上一行所有 2-face ≥ 0 的格子(蓝格)挑出来,准备相加。
把这些蓝格的值加起来取模:0 + 1 = 1。填入紫格 dp[1][2]=1。
算 dp[1][3]:第 1 个骰子掷 face(1 到 6),要凑和 3,前 0 个骰子就得凑出 3-face。把上一行所有 3-face ≥ 0 的格子(蓝格)挑出来,准备相加。
把这些蓝格的值加起来取模:0 + 0 + 1 = 1。填入紫格 dp[1][3]=1。
算 dp[1][4]:第 1 个骰子掷 face(1 到 6),要凑和 4,前 0 个骰子就得凑出 4-face。把上一行所有 4-face ≥ 0 的格子(蓝格)挑出来,准备相加。
把这些蓝格的值加起来取模:0 + 0 + 0 + 1 = 1。填入紫格 dp[1][4]=1。
算 dp[1][5]:第 1 个骰子掷 face(1 到 6),要凑和 5,前 0 个骰子就得凑出 5-face。把上一行所有 5-face ≥ 0 的格子(蓝格)挑出来,准备相加。
把这些蓝格的值加起来取模:0 + 0 + 0 + 0 + 1 = 1。填入紫格 dp[1][5]=1。
算 dp[1][6]:第 1 个骰子掷 face(1 到 6),要凑和 6,前 0 个骰子就得凑出 6-face。把上一行所有 6-face ≥ 0 的格子(蓝格)挑出来,准备相加。
把这些蓝格的值加起来取模:0 + 0 + 0 + 0 + 0 + 1 = 1。填入紫格 dp[1][6]=1。
算 dp[1][7]:第 1 个骰子掷 face(1 到 6),要凑和 7,前 0 个骰子就得凑出 7-face。把上一行所有 7-face ≥ 0 的格子(蓝格)挑出来,准备相加。
把这些蓝格的值加起来取模:0 + 0 + 0 + 0 + 0 + 0 = 0。填入紫格 dp[1][7]=0。
用了 2 个骰子还想让总和为 0?不可能,每个骰子至少掷 1 点。dp[2][0]=0(紫格)。
算 dp[2][1]:第 2 个骰子掷 face(1 到 6),要凑和 1,前 1 个骰子就得凑出 1-face。把上一行所有 1-face ≥ 0 的格子(蓝格)挑出来,准备相加。
把这些蓝格的值加起来取模:0 = 0。填入紫格 dp[2][1]=0。
算 dp[2][2]:第 2 个骰子掷 face(1 到 6),要凑和 2,前 1 个骰子就得凑出 2-face。把上一行所有 2-face ≥ 0 的格子(蓝格)挑出来,准备相加。
把这些蓝格的值加起来取模:1 + 0 = 1。填入紫格 dp[2][2]=1。
算 dp[2][3]:第 2 个骰子掷 face(1 到 6),要凑和 3,前 1 个骰子就得凑出 3-face。把上一行所有 3-face ≥ 0 的格子(蓝格)挑出来,准备相加。
把这些蓝格的值加起来取模:1 + 1 + 0 = 2。填入紫格 dp[2][3]=2。
算 dp[2][4]:第 2 个骰子掷 face(1 到 6),要凑和 4,前 1 个骰子就得凑出 4-face。把上一行所有 4-face ≥ 0 的格子(蓝格)挑出来,准备相加。
把这些蓝格的值加起来取模:1 + 1 + 1 + 0 = 3。填入紫格 dp[2][4]=3。
算 dp[2][5]:第 2 个骰子掷 face(1 到 6),要凑和 5,前 1 个骰子就得凑出 5-face。把上一行所有 5-face ≥ 0 的格子(蓝格)挑出来,准备相加。
把这些蓝格的值加起来取模:1 + 1 + 1 + 1 + 0 = 4。填入紫格 dp[2][5]=4。
算 dp[2][6]:第 2 个骰子掷 face(1 到 6),要凑和 6,前 1 个骰子就得凑出 6-face。把上一行所有 6-face ≥ 0 的格子(蓝格)挑出来,准备相加。
把这些蓝格的值加起来取模:1 + 1 + 1 + 1 + 1 + 0 = 5。填入紫格 dp[2][6]=5。
算 dp[2][7]:第 2 个骰子掷 face(1 到 6),要凑和 7,前 1 个骰子就得凑出 7-face。把上一行所有 7-face ≥ 0 的格子(蓝格)挑出来,准备相加。
把这些蓝格的值加起来取模:1 + 1 + 1 + 1 + 1 + 1 = 6。填入紫格 dp[2][7]=6。
整张表填满,右下角 dp[2][7] = 6 就是答案:用 2 个六面骰子掷出总和 7 的方案数。回头数一数:1+6、2+5、3+4、4+3、5+2、6+1,正好 6 种。
复盘整条思路:dp[i][s] 表示「前 i 个骰子凑出和 s 的方案数」,每多一个骰子就把它的 1 到 k 点从上一行累加过来,逐行往下推,右下角即答案 6。
边界:和必须落在 [n, n·k] 才有解;一个骰子时和等于点数;和等于 n 时唯一一种。
两个追问:它是恰好 n 个分组的分组背包计数;前缀和可把内层 k 优化掉。
参考代码
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]复杂度
- 时间：O(n·k·target)，n 个骰子,每个骰子枚举每个和 s(共 target 个)再枚举 k 种点数
- 空间：O(target)，滚动数组只存一行;若用完整二维表则是 O(n·target)
易错点
面试追问把动画讲成自己的话
追问这题和「完全背包 / 零钱兑换 II」有什么联系?
追问如果改成求「点数和小于等于 target」的方案数怎么办?
这道题到这就讲完了。动画和文字是同一套思路——别光看，关掉页面自己默写一遍。然后顺着主线继续：
最长定差子序列
LeetCode 1218 · 中等 · 沿着 动态规划套路 继续往下推进
把这道题真正学会，再走
图解算法年卡 ¥99 /年
- ✓本题每步动画的吴师兄语音讲解（全站陆续覆盖）
- ✓小欧带 8 步通关训练——追问到不看答案也能写对、能 30 秒讲给面试官听
- ✓学习报告，记录每道题的掌握程度
76k+ GitHub Star · 吴师兄开源图解算法，几十万开发者在看的算法讲解
想成体系刷透这类套路？去图解算法专题