标签: 动态规划
难度: Hard
Submission
运行时间: 286 ms
内存: 86.2 MB
from functools import lru_cache
MOD = 10**9 + 7
@lru_cache(None)
def dfs(n, k):
if k == 1 or n == k:
return 1
return (dfs(n - 1, k - 1) + dfs(n - 1, k) * k) % MOD
class Solution:
def waysToDistribute(self, n: int, k: int) -> int:
return dfs(n, k)
Explain
该题解使用了动态规划的方法，通过递归函数 `dfs` 来计算将 `n` 个糖果分配到 `k` 个盒子中的不同方式。如果 `k` 为1，或者 `n` 等于 `k`（即每个盒子只能放一个糖果），那么只有一种分配方式。递归关系为：`dfs(n, k) = (dfs(n - 1, k - 1) + dfs(n - 1, k) * k) % MOD`，这里 `dfs(n - 1, k - 1)` 表示新加入一个盒子放一个糖果的情况，而 `dfs(n - 1, k) * k` 表示在已有的 `k` 个盒子中任选一个放入新糖果的情况。结果通过模 `10^9 + 7` 确保不超出整数范围。
时间复杂度: O(n * k)
空间复杂度: O(n * k)
from functools import lru_cache
MOD = 10**9 + 7
@lru_cache(None)
def dfs(n, k):
# Base cases: 当只有一个盒子或者糖果数等于盒子数时，只有一种分配方式
if k == 1 or n == k:
return 1
# 递归计算分配糖果的方式，考虑新加入的糖果放入新盒子或已有盒子
return (dfs(n - 1, k - 1) + dfs(n - 1, k) * k) % MOD
class Solution:
def waysToDistribute(self, n: int, k: int) -> int:
# 入口函数，调用递归函数计算结果
return dfs(n, k)
Explore
`MOD = 10**9 + 7` 是一个大质数，常用于计算机科学中模运算的场景，主要用于避免整数溢出和减小计算结果的大小，使得结果可以被有效地存储和处理。在算法竞赛或编程问题中，使用这种大质数作为模数还可以减少哈希碰撞的可能性，提高算法效率。
将结果模 `MOD` 是为了避免在递归计算过程中产生的大数值超过编程语言的整数处理能力（例如在 Python 中虽然整数类型是动态的，但在其他语言如 Java 或 C++ 中可能会有整数溢出的问题），同时也保持结果在一个可控的范围内，减少计算和存储的复杂性。此外，模运算可以保证结果的统一性，确保数值稳定且易于比较和验证。
为了防止递归过程中栈溢出，可以使用 `@lru_cache(None)` 装饰器来实现记忆化。这个装饰器帮助存储已经计算过的函数结果，从而避免了重复的递归调用和不必要的栈深度增加。记忆化不仅可以优化递归的性能，减少计算时间，同时也大大减少了栈的使用，防止了因递归层数过深导致的栈溢出问题。