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

约 5 分钟
文章信息 8 个分类 1 个标签
分类
LeetCode CodeTop 中等 未解决 2-5 字节 阿里 微软
标签
动态规划

题目描述

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

image-20260928230029032

image-20260928230029033

题意分析

有 n 个骰子，每个骰子的点数都在 1..k，每个骰子恰好掷一次，统计总点数恰好等于 target 的方法数，答案对 10^9 + 7 取模。

不同骰子可以区分，给各个骰子分配的点数不同就算不同方案，不能只把点数集合相同的结果合并。必须恰好使用 n 个骰子，既不能少掷，也不能让某个骰子取零点。目标小于 n 或大于 n × k 时自然无解。

解法：滚动数组动态规划

核心思路

[!blue]

按已经掷过的骰子数量分层。设 ways[dice][sum] 表示前 dice 个骰子掷出总和 sum 的方案数。最后一个骰子的点数若为 face，前面的骰子就必须凑出 sum - face，因此把旧层所有合法 ways[dice - 1][sum - face] 相加即可。

按最后一个骰子的点数分类，不同 face 的方案互不重叠，每种完整结果又都有唯一的最后点数，所以转移不重不漏。每种点数只能在 1..k 内，并且不能超过当前总和，避免读取负下标。

初始时零个骰子凑出零有一种方法，即什么都不掷，因此 dp[0] = 1；零个骰子凑其他和则为零。这个空方案是第一颗骰子产生计数的起点，不代表以后仍可用掷过的骰子凑零。

每一层只依赖上一层，可以用 dp 保存旧层、next 保存新层。每次新建的 next 从零开始，尤其 next[0] 必须保持零，因为已经掷过骰子后总和至少为一。整层计算完再用 next 替换 dp，防止同一个骰子通过读取本轮结果被重复使用。

计数增长很快，需要在转移中取模。Java 每个总和用 long 汇总当前至多 k 个模内计数后取模；Go 在每次累加后取模，使累加值保持在安全范围内。处理完恰好 n 层后，目标位置就是答案。

解题步骤

  1. 创建长度为 target + 1 的数组 dp，只有 dp[0] = 1。
  2. 对每个骰子创建新的全零数组 next。
  3. 枚举目标总和 sum = 1..target，再枚举 face = 1..min(k, sum)。
  4. 将旧层的 dp[sum - face] 累加为新层该总和的计数，按代码方式及时取模。
  5. 全部总和计算完后令 dp = next，继续下一颗骰子。
  6. 完成 n 层后返回 dp[target]，不可达状态会一直保持为零。

代码实现

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(nkT)，其中 T = target。每一颗骰子更新至多 T 个总和，每个总和枚举至多 k 个点数。
  • 空间复杂度：O(T + 1)。任意时刻只保留新旧两层数组，不需要保存全部骰子层。

关键点总结

[!green]

  • 骰子数量必须作为层次，才能表达“恰好掷 n 次”。
  • 按最后点数分类产生有序结果计数，交换不同骰子的点数通常对应另一方案。
  • 空方案只存在于零骰子的初始层，后续零和应不可达。
  • 分开新旧层避免本轮骰子被重复使用。

易错点总结

[!yellow]

  • 初始 dp[0] 为零：第一颗骰子没有计数来源，全部结果都会保持零。
  • 新层沿用旧层数值：相当于允许少掷骰子，必须从新的全零数组开始。
  • 新层零和仍设为一：会允许已经使用的骰子取零点，不符合点数范围。
  • 原地正序累加状态：可能读取本轮刚产生的计数，重复使用同一颗骰子。
  • 点数枚举超过 sum：旧层下标会变成负数，需要同时受点数上限和当前总和限制。
  • 只在最终答案处取模：中间计数可能已经溢出，必须在转移期间控制数值。

相似题目

题目 难度 关联与区别
377. 组合总和 Ⅳ 中等 同样计有序选择方案，本题额外固定恰好投掷n次，因此要记录已用骰子数。
1223. 掷骰子模拟 困难 同样计骰子结果序列，原题限制连续点数长度，本题限制点数总和。
转载与许可
作者
链接 https://hgnulb.github.io/blog/2022/80978117
许可 本博客所有文章除特别声明外，均采用 CC BY-NC-SA 4.0 许可协议，转载请注明出处！