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

2022-03-07 HGNULB 约 9 分钟

文章信息 8 个分类 1 个标签

分类

题目描述

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

题意分析

有 n 个骰子，每个骰子有 k 个面，点数从 1 到 k。问掷完全部 n 个骰子、点数之和恰好等于 target 的不同结果有多少种，答案对 $10^9 + 7$ 取模。

「不同结果」是按骰子区分的：骰子有先后之分，第一个掷 1、第二个掷 2 与第一个掷 2、第二个掷 1 算两种。这决定了它是排列计数而不是组合计数，也决定了转移时要按「第几个骰子」逐层推进，而不是按「点数从小到大」做完全背包。

要求取模是一条明确信号：方案数会大到爆 int，中间每一步都得取模，而不是最后才取。

数据规模 n、k、target 都在 30 到 1000 的量级，三重循环 $O(n \cdot k \cdot target)$ 是可以接受的。

边界包括：n 个骰子的点数和必然落在 [n, n·k] 内，target 在区间外时答案是 0；点数最小为 1 而不是 0，所以每个骰子至少贡献 1，dp[0] 在掷过骰子之后必须归零。

解法：滚动数组动态规划

核心思路

暴力做法是递归枚举每个骰子的点数，走到底再判断总和是否等于 target，复杂度 $k^n$，n 稍大就完全跑不动。观察递归树会发现大量重复：不同的前缀只要「已掷骰子数」和「当前累计和」相同，剩下的子问题就完全一样，被反复重算。

这两个量恰好构成充分的状态——具体是哪几个骰子掷出了什么点数，对后续没有任何影响。于是定义 f[i][s] 表示用前 i 个骰子掷出总和恰好为 s 的方案数。

转移就是枚举第 i 个骰子的点数 face：f[i][s] = Σ_{face=1..k, face<=s} f[i-1][s-face]。含义是「第 i 个骰子掷出 face，那么前 i-1 个骰子必须凑出 s-face」，这些情形互不相交且覆盖全部可能，所以直接求和。初值 f[0][0] = 1，表示一个骰子都没掷时总和为 0 有且只有一种方式（什么都不做），其余 f[0][s] = 0。

再看依赖：第 i 层只用到第 i-1 层，二维表里其余层全是死数据，因此可以只留一行。但这里不能像完全背包那样在原数组上原地滚动——本题每个骰子只能用一次，如果原地更新，同一轮里刚写好的新值会被当作旧值再次使用，等于让一个骰子被重复计数。所以每轮新开一个 next 数组，算完整轮再整体替换。

由此得到的不变量是：每轮循环结束时，dp 数组恰好表示「用 dice 个骰子掷出各个总和的方案数」，其中已掷骰子数由外层循环唯一确定。next 数组的引入正是为了让「读的全是上一轮、写的全是这一轮」这条性质严格成立。

解题步骤

开长度 target + 1 的数组 dp，令 dp[0] = 1，其余为 0。这代表零个骰子的初始状态，是整个递推的种子；写成 1 而不是 0，是因为「什么都不掷得到和 0」是一种合法方案，不是无方案。

外层按骰子数从 1 到 n 循环，每轮新建全 0 的 next 数组。新建而不是复用，既保证了新旧状态分离，也顺带把「本轮无法达成的和」自动置为 0。

内层遍历总和 s 从 1 到 target。从 1 开始而不是从 0 开始，是因为掷了至少一个骰子后总和不可能为 0，next[0] 必须保持 0——这正是「点数最小为 1」这条题意的落地。

最内层枚举本次骰子的点数 face 从 1 到 k，同时要求 face <= s，把 dp[s - face] 累加进来。face <= s 这个条件防止下标为负，也表达了「点数不能超过要凑的和」。

累加过程用 long（Go 里及时取模）承接，写回时再取模。k 最大 1000，每项都接近模数时朴素相加会超过 int 范围，必须用更宽的类型或每步取模。

一轮算完把 dp 指向 next，进入下一个骰子。全部处理完返回 dp[target]。

以 n = 2、k = 6、target = 7 走一遍，dp 长度为 8，初始 dp = [1,0,0,0,0,0,0,0]。

第一个骰子（dice = 1）：新建 next 全 0。s = 1 时枚举 face = 1，累加 dp[0] = 1，得 next[1] = 1；face 到 2 时因 face > s 停止。s = 2 时 face = 1 累加 dp[1] = 0，face = 2 累加 dp[0] = 1，得 next[2] = 1。同理 s = 3 到 6 都得到 1。s = 7 时 face 从 1 到 6，对应 dp[6] 到 dp[1] 全是 0，得 next[7] = 0——一个骰子掷不出 7，符合直觉。此轮结束 dp = [0,1,1,1,1,1,1,0]，注意 dp[0] 已经从 1 变成 0。

第二个骰子（dice = 2）：我们关心的是 next[7]。枚举 face = 1 到 6，分别累加 dp[6] = 1、dp[5] = 1、dp[4] = 1、dp[3] = 1、dp[2] = 1、dp[1] = 1，合计 6，所以 next[7] = 6。

返回 dp[7] = 6，对应 (1,6)、(2,5)、(3,4)、(4,3)、(5,2)、(6,1) 六种有序结果，与题目样例一致。

这一步也说明了「有序」的含义：(1,6) 和 (6,1) 被分别计入，正是因为外层按骰子编号逐个推进，天然区分了先后。

代码实现

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 dice = 1; dice <= n; dice++) {
            int[] next = new int[target + 1];
            for (int sum = 1; sum <= target; sum++) {
                long ways = 0;
                for (int face = 1; face <= k && face <= sum; face++) {
                    ways += dp[sum - face];
                }
                next[sum] = (int) (ways % mod);
            }
            dp = next;
        }

        return dp[target];
    }
}

func numRollsToTarget(n int, k int, target int) int {
    const mod = 1000000007
    dp := make([]int, target+1)
    dp[0] = 1

    for dice := 1; dice <= n; dice++ {
        next := make([]int, target+1)
        for sum := 1; sum <= target; sum++ {
            ways := 0
            for face := 1; face <= k && face <= sum; face++ {
                ways = (ways + dp[sum-face]) % mod
            }
            next[sum] = ways
        }
        dp = next
    }

    return dp[target]
}

复杂度分析

时间复杂度：$O(n \cdot k \cdot target)$，三层循环分别枚举骰子编号、目标和、本次点数，每层内部只有常数次加法与取模。

空间复杂度：$O(target)$，滚动之后同时只存在上一轮和当前轮两个长度为 target + 1 的数组；不滚动的二维写法则是 $O(n \cdot target)$。

关键点总结

计数型 DP 的状态定义要落在「已处理多少个物品」和「当前累计量」这两个维度上，转移是把「本次取什么」的所有互斥情形求和，这套模板同样适用于组合总和、目标和、零钱兑换 II。

初值 f[0][0] = 1 是计数 DP 的通用起点，它表达的是「空方案算一种」，把它写成 0 会让整张表全是 0。

每个物品只能用一次时，滚动数组必须用「新旧两份」或「倒序更新」，直接正序原地更新会让同一个骰子被重复使用，答案偏大。

取模要在每次累加或写回时立即做，并留意累加过程本身的溢出——k 个接近 $10^9$ 的数相加早已超出 int，必须先升到 long 或每步取模。

面试视角：面试官通常先问朴素递归，再引导你加记忆化，最后要求改成迭代加滚动数组，这三步都要能说清楚。被追问优化时可以提：内层求和是一个长度为 k 的滑动窗口，用前缀和可以把复杂度降到 $O(n \cdot target)$，这是本题最漂亮的加分项。

易错点总结

错误写法：dp[0] 初始化为 0 → 用例 n = 1, k = 6, target = 3，没有任何种子值可供转移，整张表恒为 0，返回 0，正确答案是 1。

错误写法：内层 sum 从 0 开始，让 next[0] 也参与转移或保留旧值 → 用例 n = 2, k = 6, target = 7，dp[0] 在掷过骰子后仍为 1，第二轮会多算出「有一个骰子掷了 0 点」的非法方案，结果偏大。

错误写法：在同一个 dp 数组上正序原地更新 → 用例 n = 2, k = 6, target = 7，第一轮写好的 dp[1] 立刻被第二轮读取，等价于同一个骰子被用多次，返回的是完全背包的方案数而非 6。

错误写法：漏掉 face <= sum 的限制 → 用例 n = 1, k = 6, target = 3，face = 4 时访问 dp[-1]，Java 抛数组越界、Go 直接 panic。

错误写法：累加用 int 且只在最后取模 → 用例 n = 30, k = 1000, target = 1000，一轮内最多累加 1000 个接近 $10^9$ 的数，int 溢出成负数，答案完全错误。

错误写法：只在返回时取一次模 → 用例同上，中间层的数值早已溢出，最后再取模也救不回来。

错误写法：把 face 的上界写成 face <= k 却忘了 k 可能大于 target → 逻辑上被 face <= sum 挡住了，但若两个条件写成或的关系（face <= k || face <= sum），用例 n = 1, k = 1000, target = 3 会越界访问。

错误写法：认为答案与顺序无关，除以骰子数的阶乘去重 → 用例 n = 2, k = 6, target = 7，把 6 除以 2 得 3，但题目区分骰子顺序，正确答案就是 6。

错误写法：忘记 target 可能小于 n 或大于 n·k 时无解，且在建数组前未判断 → 用例 n = 30, k = 30, target = 500，虽然本写法会自然返回 0，但若有人「优化」成从 dp[target] 倒推并假设一定有解，就会得到错误的非零值。

错误写法：外层循环写成 for dice = 0; dice < n; dice++ 却在内层用 dice 做下标 → 用例任意，层数与下标含义错位，最终读到的是第 n-1 层的结果，少掷了一个骰子。

错误写法：Go 里把 dp = next 写成 copy(dp, next) 之前忘了清零 next 的复用 → 若把 next 提到循环外复用而不每轮清零，用例 n = 2, k = 6, target = 7 会把上一轮的方案数继续累加，返回值偏大。

相似题目

题目	难度	考察点
剑指 Offer 60. n个骰子的点数	中等	面数固定为 6，要求输出所有点数的概率分布而非单个方案数
377. 组合总和 Ⅳ	中等	物品可无限次使用，外层循环换成总和才能得到有序排列数
518. 零钱兑换 II	中等	同为计数但要求组合不计顺序，外层必须循环硬币
494. 目标和	中等	每个数只能加或减，可转化成子集和计数的 0-1 背包
322. 零钱兑换	中等	求最少枚数而非方案数，初值改为无穷大且转移取最小
279. 完全平方数	中等	物品集合由平方数隐式生成，同样是求最少个数
416. 分割等和子集	中等	只需判定可达性，状态可压成布尔并用倒序更新
1049. 最后一块石头的重量 II	中等	转化成尽量接近半和的背包，答案取两部分之差
LCR 103. 零钱兑换	中等	322 的中文版，适合对照记忆化搜索与迭代两种写法