第十五届蓝桥杯第三期模拟赛 《台阶问题》

小蓝要上一个楼梯，楼梯共有 n 级台阶（即小蓝总共要走 n 级）。小蓝每一步可以走 a 级、b 级或 c 级台阶。
请问小蓝总共有多少种方案能正好走到楼梯顶端？

输入格式

输入的第一行包含一个整数 n 。
第二行包含三个整数 a, b, c 。

输出格式

输出一行包含一个整数，表示答案。答案可能很大，请输出答案除以 1000000007 后的余数。

问题类型

线性DP

问题分析

将一条线段看作是方案总数，设T[n]表示小蓝走到第n个台阶时的方案总数。如图：

上图中黄色代码块为理想情况下(即一次可以走a、b、c三种方案)的思路。
如果我们需要走到第i个台阶（假设i为较接近n但小于n的数，远大于每次可走的台阶数的最大值），其共可以是三种情况：从第i-a个台阶处、第i-b个台阶处、第i-c个台阶处分别上a、b、c个台阶。
所以我们需要知道当走到第i个台阶时共有多少种方案，在理想情况下，只需要知道走到第i-a个台阶处、第i-b个台阶处、第i-c个台阶处时分别有多少种方案，在三个台阶处的方案数基础上分别加1就是走到第i个台阶处的方案总数。
按此思路依次往前推导，假设a、b、c中a最小，则当i<a时，T[i] = 0。当i==a or i == b or i == c 时，T[i] = 1，这是因为在这三种情况下（不考虑a、b、c之间存在倍数关系），小蓝都是直接从第零个台阶处开始上楼梯的，我们需要判断i是否等于这三个数。

代码实现

n = int(input())
a, b, c = map(int, input().split())
T = [0] * (n + 1) # 可以看出在定义时T[0]的含义不明
# 必须清楚T[n]的含义是在走到第n个台阶时，实现上到第n个台阶的方案总数
mod = 1000000007
for i in range(min(a, b, c), n + 1):
    if i in (a, b, c):  # 我们可以省去此if语句，直接将T[0]赋值为1，则当i为a或b或c时可直接进行下面的三个自增操作
        T[i] = 1
    if i >= a:
        T[i] += T[i - a]
    if i >= b:
        T[i] += T[i - b]
    if i >= c:
        T[i] += T[i - c]
print(p[n] % mod)
# 代码实现较为抽象，不理解请多看几遍