会员专享
请先
登录，登录后可使用今日免费解锁；
开通会员后可解锁完整内容。
解题思路
本题要求计算满足约束条件的步长序列数量。约束为：每一步可以是 1 米或 2 米，总距离恰好为 k 米；必须保证第一步不是 1 米，除非整个序列只有一步（即 k=1，此时步长为 1 米是允许的）。
-
特判 k=1：只有一种方案 [1]，故答案为 1。
-
对于 k≥2，由于第一步不能是 1，第一步必须是 2 米。第一步走完后，剩余距离为 k−2 米。剩余部分可以任意使用 1 米和 2 米的步长，没有任何额外限制。
-
定义 g(n) 为用 1 米和 2 米的步长走完 n 米的总方案数（步长顺序不同视为不同方案）。显然有：
