洛谷 P1192 台阶问题 题解【递推】
点击量:329
– 分析:本题是一个递推的问题,即有n个方案到一个点,那么这个点能到达的点一定有这n个方案。其中加上这一步,方案数没有改变。
– 而且,由不同的点到某一个目标点,方案一定不同,因为这些方案的倒数第二个点不同,所以这些是可以累加的。
– 解决方案:从左向右递推,既然已经扫描到某个点,那么它前面的点一定被扫描过。而一个点的状态只能由它前面的点推过来,所以一直递推到最后。
– 注意事项:这种做法不用特殊处理的话数组要开到[n+k+],因为for循环里的i+j最大就是n+k;最终结果是f[n],后面的数据就不需要了。如果特判i+j<=n的话可能会浪费复杂度为k的时间,所以是要么利用空间的k要么利用时间的k。
– 下面贴代码
#include <cstdio>
#include <cstring>
using namespace std;
int f[100101];
int main()
{
int n,m;
scanf("%d%d",&n,&m);
memset(f,0,sizeof(f));
f[0]=1;
for(int i=0;i<=n;i++)
for(int j=1;j<=m;j++)
{
f[i+j]+=f[i];
f[i+j]%=100003;
}
printf("%d\n",f[n]);
return 0;
}
说点什么