如何优化Python骰子组合计数DP代码，提升大n值下运行速度？

你的递归式DP在n较大时超时，核心问题是递归调用的栈开销过大，加上每次计算需要循环6次的常数开销。下面给出两种针对性的优化方案：

方案1：改用迭代式自底向上DP #

递归的函数调用在n=65万时会产生巨大的栈开销，换成循环迭代的方式，直接从底向上计算每个dp值，彻底消除递归的额外开销。

代码示例：

MOD = 10**9 + 7

n = int(input())
dp = [0] * (n + 1)
dp[0] = 1  # 初始条件：组成0的方式只有1种（不选任何骰子）

for i in range(1, n + 1):
    # 累加前6个状态的值
    for j in range(1, 7):
        if i - j >= 0:
            dp[i] = (dp[i] + dp[i - j]) % MOD

print(dp[n])

方案2：简化递推公式，进一步提速 #

观察递推关系可以发现：

• 当i >=7时，dp[i] = dp[i-1] + dp[i-2] + dp[i-3] + dp[i-4] + dp[i-5] + dp[i-6]
• 而dp[i-1] = dp[i-2] + dp[i-3] + dp[i-4] + dp[i-5] + dp[i-6] + dp[i-7]

将两式相减可得：dp[i] = 2 * dp[i-1] - dp[i-7]（注意减法要处理负数，避免模运算后出现负数值）

这个优化把内层循环的6次计算简化为1次算术运算，时间复杂度的常数项大幅降低，运行速度会比方案1更快。

代码示例：

MOD = 10**9 + 7

n = int(input())
if n == 0:
    print(1)
    exit()

# 初始化dp数组，大小覆盖到n即可
dp = [0] * (n + 1)
dp[0] = 1

# 先计算前6项（i<7时，直接累加所有合法的前驱状态）
for i in range(1, min(7, n + 1)):
    for j in range(1, i + 1):
        dp[i] = (dp[i] + dp[i - j]) % MOD

# 从第7项开始用简化公式计算
for i in range(7, n + 1):
    dp[i] = (2 * dp[i-1] - dp[i-7]) % MOD
    # 处理减法可能产生的负数
    if dp[i] < 0:
        dp[i] += MOD

print(dp[n])

原代码超时的原因 #

递归自顶向下的方式，每一次函数调用都要保存栈帧、处理参数传递，当n达到65万时，这些累积的开销会拖慢程序运行速度。而迭代式的方式完全避免了递归调用的额外开销，同时简化递推公式进一步减少了计算量，能轻松处理n=65万的场景。

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