Dice Combinations 题解

题目描述

https://cses.fi/problemset/task/1633

给定一个目标整数 N，计算有多少种骰子投掷序列，使得骰子顶面的和为 N。

限制：1 ≤ N ≤ 10⁶

---

解法

问题类型：完全背包（计数问题，每种骰子点数可用无限次）

定义：dp[i] 为掷骰子得到的和为 i 的所有序列的数量

初始条件：dp[0] = 1（和为 0 只有一种方式：什么都不投），当 i < 0 时忽略

状态转移： dp[i] = dp[i − 1] + dp[i − 2] + dp[i − 3] + dp[i − 4] + dp[i − 5] + dp[i − 6]

解释：考虑最后一个掷出的骰子点数。如果是 1，则前面和为 i − 1；如果是 2，则前面和为 i − 2；… 依此类直到 6。将所有可能的情况相加。

代码

MOD = 10**9 + 7
n = int(input())
dp = [1]

for i in range(n):
    total = sum(dp[-6:])
    dp.append(total % MOD)

print(dp[-1])

时间复杂度：O(N) 空间复杂度：O(N)