蓝桥杯备考：动态规划线性dp之下楼梯问题进阶版

老规矩，按照dp题的顺序

step1 定义状态表达  f[i]表示到第i个台阶的方案数

step2:推导状态方程

step3:初始化 初始化要保证 1.数组不越界 2.推导结果正确

如图这种情况就越界了，我们如果把1到k的值全初始化也不现实，会增加程序的时间复杂度

我们可以这样，我们把数组下标为0的位置设置成1，那么f[1]=f[0] f[2] = f[1]+f[0]=2 

f[3] = f[0]+f[1]+f[2] = 4      这个是可以的

step4:找结果

这个结果就是f[n]的值

代码：

#include <iostream> using namespace std; const int N = 1e5+10,mod=1e5+3; int f[N]; int n,k; int main() { cin >> n >> k; f[0] = 1; for(int i = 1;i<=n;i++) { for(int j = 1;j<=k&&i-j>=0;j++) { f[i] +=f[i-j]; } f[i]%=mod; } cout << f[n] << endl; return 0; }