蓝桥杯备考：动态规划线性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;
}
北京人形旗下天工造物具身智能开源社区，聚焦具身天工与慧思开物两大平台
更多推荐
1
0- 0
已为社区贡献6条内容
所有评论(0)