优化非递减分糖果分配计数算法：解决超时问题

问题分析 #

你的任务本质是求将C个糖果分给D个孩子，满足非递减分配（对应示例中的方案）的方案数，这等价于求整数分拆中允许前导零、最多拆分为D个部分的方案数。

原递归实现的问题是暴力枚举所有可能的分配组合再筛选，时间复杂度为指数级，完全无法处理D≥10、C≥100的情况；你的DP版本虽然正确，但每次查询都重新计算整个DP表，Q=1000次查询会导致大量重复计算，这是超时的核心原因。

优化思路 #

核心优化点是预处理所有可能的D（1_{100）和C（1}5000）的结果，将结果存储在二维数组中，之后每个查询直接查表即可，实现O(1)的查询时间。预处理仅需一次，时间复杂度为O(D_maxC_max)=1005000=500,000次操作，完全在合理范围内。

优化后的代码 #

MOD = 2 ** 30 - 1
MAX_D = 100
MAX_C = 5000

# 预处理DP表：dp[d][c]表示d个孩子分c个糖果的符合要求的方案数
dp = [[0] * (MAX_C + 1) for _ in range(MAX_D + 1)]
dp[0][0] = 1

for d in range(1, MAX_D + 1):
    for c in range(MAX_C + 1):
        # 情况1：第d个孩子分0个糖果，等价于d-1个孩子分c个糖果的方案数
        dp[d][c] = dp[d-1][c]
        # 情况2：第d个孩子至少分1个糖果，此时每个孩子都可以减少1个糖果，总糖果数变为c-d
        if c >= d:
            dp[d][c] += dp[d][c - d]
        # 取模避免溢出
        dp[d][c] %= MOD

# 处理查询
q = int(input().strip())
for _ in range(q):
    d, c = map(int, input().split())
    print(dp[d][c])

代码解释 #

1. 预处理阶段：
   • dp[d][c]定义为d个孩子分c个糖果的符合要求的方案数。
   • 状态转移分为两种情况：
     • 若第d个孩子分0个糖果，方案数等于d-1个孩子分c个糖果的方案数（dp[d-1][c]）。
     • 若第d个孩子至少分1个糖果，我们可以给每个孩子都减去1个糖果（保持非递减性质），此时总糖果数变为c-d，方案数等于dp[d][c-d]。
   • 每次计算后取模，避免数值溢出。
2. 查询阶段：
   • 直接从预处理好的dp数组中取对应d和c的值，输出即可，每个查询仅需O(1)时间。

性能对比 #

• 原DP版本：1000次查询总操作数约为10001005000=5e8次。
• 优化版本：仅需5e5次预处理操作，加上1000次O(1)查询，总操作数不到6e5次，性能提升近千倍。

内容的提问来源于stack exchange，提问作者Oerlikon