题解 P1192 【台阶问题】

- 分析：本题是一个递推的问题，即有n个方案到一个点，那么这个点能到达的点一定有这n个方案。其中加上这一步，方案数没有改变。 - 而且，由不同的点到某一个目标点，方案一定不同，因为这些方案的倒数第二个点不同，所以这些是可以累加的。 - 解决方案：从左向右递推，既然已经扫描到某个点，那么它前面的点一定被扫描过。而一个点的状态只能由它前面的点推过来，所以一直递推到最后。 - 注意事项：这种做法不用特殊处理的话数组要开到[n+k+]，因为for循环里的i+j最大就是n+k;最终结果是f[n]，后面的数据就不需要了。如果特判i+j<=n的话可能会浪费复杂度为k的时间，所以是要么利用空间的k要么利用时间的k。 - 下面贴代码 ```cpp #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; } ```