标签: 动态规划
难度: Medium
这里有 n 个一样的骰子，每个骰子上都有 k 个面，分别标号为 1 到 k 。
给定三个整数 n、k 和 target，请返回投掷骰子的所有可能得到的结果（共有 kn 种方式），使得骰子面朝上的数字总和等于 target。
由于答案可能很大，你需要对 109 + 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 解释：返回的结果必须对 109 + 7 取模。
提示：
1 <= n, k <= 301 <= target <= 1000运行时间: 32 ms
内存: 0.0 MB
class Solution:
def numRollsToTarget(self, n: int, k: int, target: int) -> int:
if target < n or n * k < target:
return 0
alt = lambda i, m: (-comb(n, i) if i & 1 else comb(n, i)) * comb(m, n - 1)
return sum(starmap(alt, enumerate(range(target - 1, n - 2, -k)))) % 1000000007
该题解使用了组合数学的概念，特别是通过包容排斥原理来计算可能的骰子和。思路基于找到所有可能使得 n 个骰子的和为 target 的组合数。它使用了一个 lambda 函数 `alt` 来计算给定的序号 i 和对应的 m 值的组合数，根据奇偶性决定是否需要负号。然后，它枚举了一个范围内所有可能的组合，并对结果求和后取模 1000000007。该范围是通过从 target-1 开始向下每次减少 k 遍历到 n-2 的过程。这种方式利用数学原理简化了直接的动态规划算法的计算复杂度。
时间复杂度: O((target-n)/k * min(n, m-n))
空间复杂度: O(1)
class Solution:
def numRollsToTarget(self, n: int, k: int, target: int) -> int:
# 如果目标不可达，返回0
if target < n or n * k < target:
return 0
# alt 函数计算包容排斥中的每一项
alt = lambda i, m: (-comb(n, i) if i & 1 else comb(n, i)) * comb(m, n - 1)
# 枚举所有可能的组合，并求和
return sum(starmap(alt, enumerate(range(target - 1, n - 2, -k)))) % 1000000007
使用包容排斥原理而不是动态规划方法的主要原因是计算效率和复杂性。动态规划方法虽然直观，但需要构建和维护一个较大的状态空间表，对于大量的骰子和大的目标值来说，空间和时间复杂度都比较高。而包容排斥原理通过数学公式直接计算出可能的结果，可以在不枚举所有可能性的情况下，快速得到答案，尤其是在目标值较大时更为有效。这种方法减少了计算的复杂度，使得问题可以在可接受的时间内得到解决。
组合函数`comb`的正确性通常依赖于它的数学定义和实现方式。在大多数编程环境中，例如Python的`math.comb`或使用公式计算的方法，都已经进行了优化和错误检查，确保计算的准确性。为了提高效率，通常使用了缓存机制或预计算组合数表的方法，尤其是在需要频繁调用大量组合数的场景中。此外，对于较大的数值，可能还会使用模运算来避免整数溢出，确保计算结果的稳定性和精确性。
这种枚举范围和步长的设置是为了有效地计算可能的骰子和达到目标值的组合数。从`target-1`开始向下每次减少`k`，是因为我们考虑减去一个骰子可能的最大值（即`k`），这样可以逐步减少和的数量，直到不可能再通过增加骰子来达到目标值。这种方法是基于最小化计算步骤和避免不必要的计算，因为如果剩余骰子的最大可能和都无法达到当前目标，那么继续计算更小的和是没有意义的。
函数`alt`中使用的负号是基于包容排斥原理的数学逻辑。在包容排斥原理中，为了计算不重复的组合数，需要对重叠的部分进行减法处理。具体来说，当枚举到奇数个元素的组合时，这些组合被认为是多余的重叠部分，需要从总和中减去。而偶数个元素的组合则相反，它们修正了这种重叠，需要加回到总和中。这种交替加减的处理方式是为了确保每一个组合都只被恰当地计算一次，从而得到正确的结果。