Dice Combinations 题解

题目描述

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

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

限制：$1 \le N \le 10^6$

---

解法

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

定义：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)