🌟 蓝桥杯备赛打卡(Day4) – 经典DP与组合计数：小蓝的现场问答 🏆
博主碎碎念： 大家好！这里是蓝桥杯备赛打卡 Day2！今天我们来死磕一道非常经典的组合计数与动态规划（DP）问题。这道题乍一看无从下手，但只要我们冷静下来，将大问题拆解为状态机的模式，找出状态转移的规律，就会豁然开朗。话不多说，直接看题！💪
一、 题目回顾
题目描述： 小蓝正在参与一个现场问答节目。活动中一共有 30 道题目，每题只有答对和答错两种情况。
- 每答对一题得 10 分。
- 答错一题分数归零。
- 最高奖项需要 100 分，到达 100 分时直接停止答题。
- 小蓝可以在任意时刻结束答题并领奖（可能不到 100 分）。 已知条件： 小蓝最终实际获得了 70分 对应的奖项。 问题： 请问小蓝所有可能的答题情况有多少种？
二、 核心解题思路（剥洋葱分析法）
想要最终停在 70 分，说明小蓝在答题结束时，状态必须被严格卡死。我们可以把答题过程当成一个由“对（O）”和“错（X）”组成的字符串。 要获得最终的 70 分，必须满足以下几个核心条件：
- 特例：小蓝总共就只答了 7 道题，且全对。
总结答题序列的两种形态：
- 形态一（秒杀局）： 小蓝只答了 7 道题，序列为 OOOOOOO。这种情况只有 1 种。
- 形态二（持久战）： 小蓝总共答了
i
i
i 道题（其中8
≤
i
≤
30
8 \\le i \\le 30
8≤i≤30）。- 最后的 8 道题被死死固定为：X OOOOOOO。
- 前面剩下的前缀长度为
i
−
8
i – 8
i−8。这个前缀序列随便怎么排，只要不出现连续的 10 个 O 即可。 🎯 破题关键： > 题目转化成了求：长度为 n 且不包含连续 10 个“对(O)”的序列总数。（其中 n 的取值范围是从 0 到 30−8=22）
三、 动态规划（DP）推导
我们设
d
p
[
i
]
dp[i]
dp[i] 为：长度为
i
i
i 且不包含连续 10 个“O”的序列数量。 考虑我们在长度为
i
−
1
i-1
i−1 的合法序列后追加一道题：
i
−
1
i-1
i−1 长度合法，追加 X 肯定合法。数量为
d
p
[
i
−
1
]
dp[i-1]
dp[i−1]。
d
p
[
i
−
1
]
dp[i-1]
dp[i−1]。但是！有可能会因为这最后一个 O，恰好在尾部凑成了 10 连对，导致序列失效。 什么时候会恰好凑成 10 连对？ 当且仅当它前面的序列是以 X OOOOOOOOO（1 个错 + 9 个对）结尾的。 这种“导致失效”的序列前缀部分长度为
i
−
1
−
9
=
i
−
10
i – 1 – 9 = i – 10
i−1−9=i−10。 但要注意，这 9 个 O 前面的那个必然是 X（长度算在
i
−
11
i-11
i−11 里面了），所以非法的组合数量等同于长度为
i
−
11
i-11
i−11 的合法序列数量，即
d
p
[
i
−
11
]
dp[i-11]
dp[i−11]。 🔥 状态转移方程得出：
d
p
[
i
]
=
2
×
d
p
[
i
−
1
]
−
d
p
[
i
−
11
]
dp[i] = 2 \\times dp[i-1] – dp[i-11]
dp[i]=2×dp[i−1]−dp[i−11]
初始状态处理：
- 当
i
<
10
i < 10
i<10 时，不可能凑出 10 连对，随便排：d
p
[
i
]
=
2
i
dp[i] = 2^i
dp[i]=2i - 当
i
=
10
i = 10
i=10 时，总共有2
10
=
1024
2^{10} = 1024
210=1024 种组合，只有 OOOOOOOOOO 这一种不合法：d
p
[
10
]
=
1023
dp[10] = 1023
dp[10]=1023
四、 Python3 代码实现
理清了状态转移，代码简直是水到渠成。
def solve():
# 最大允许的前缀长度为 30 – 8 = 22
max_prefix_len = 22
# dp[i] 表示长度为 i 的序列中，不包含连续 10 个“对”的序列总数
dp = [0] * (max_prefix_len + 1)
# 前缀长度为0时，相当于空序列，只有1种情况
dp[0] = 1
for i in range(1, max_prefix_len + 1):
if i <= 9:
# 长度不到10，绝对不会触发10连对提前结束，直接翻倍
dp[i] = dp[i–1] * 2
elif i == 10:
# 恰好长度为10，需要减去全部都是“对”的这一种极端情况
dp[i] = dp[i–1] * 2 – 1
else:
# 长度大于10，在追加基础上，减去尾部恰好凑成10连对的非法序列数 (dp[i-11])
dp[i] = dp[i–1] * 2 – dp[i–11]
# 总情况数 = 1 (特例：只答了7题且全对) + sum(dp) (所有可能的前缀情况总和)
total_ways = 1 + sum(dp)
print(f"小蓝所有可能的答题情况共有: {total_ways} 种")
if __name__ == '__main__':
solve()
💡 运行结果
执行上述代码，最终的答案是：8335366。
五、 复杂度分析
- 时间复杂度：
O
(
N
)
O(N)
O(N)。在这个问题中N
N
N 仅仅是前缀的最大长度 22。循环 22 次，时间复杂度极低，完全满足蓝桥杯对时间的苛刻要求。 - 空间复杂度：
O
(
N
)
O(N)
O(N)。开辟了一个长度为 23 的一维 DP 数组，消耗的内存微乎其微。
六、 备赛总结
这道题其实是爬楼梯（斐波那契数列）的一种高阶变体。难点不在于代码怎么写，而在于前期对题目场景的解构能力。 做这类题目的小技巧：
