台阶问题

题目描述

有 \(N\) 级台阶，你一开始在底部，每次可以向上迈 \(1\sim K\) 级台阶，问到达第 \(N\) 级台阶有多少种不同方式。

输入格式

两个正整数 \(N,K\)。

输出格式

一个正整数 \(ans\pmod{100003}\)，为到达第 \(N\) 级台阶的不同方式数。

样例

输入

5 2

输出

8

数据范围

对于 \(100\%\) 的数据，\(1\leq N\leq100000\)，\(1\leq K\leq100\)。

思路

和走楼梯很类似，可以把走楼梯问题看作这题K=2的特殊情况

我们可以用和走楼梯一样的分析方法：

每次可以前进1~K级台阶，那么在第 i 级台阶，可以是从第 i - 1 级到第 i - k 级的任意台阶迈过来，这样迈到第 i 级台阶的方案数就是迈到第 i - 1, i - 2, i - 3... i -k 级台阶的方案数之和，所以\(f[i]= f[i-1]+f[i-2]+...+f[i-k]\)

分析时间复杂度：

由于几乎每一个 i 都要枚举 K 个数，所以时间复杂度为\(O(K*N)\)，最大为\(10^7\)，不会超时

边界情况：

显然第1级方案数为1，而对高度小于K的台阶显然不可能从第 -1 -2 -3等幽默的台阶迈过来，所以记得2~ K-1 级台阶是\(\sum_{0}^{i-1}f[j]\)而不是\(\sum_{i-k}^{i-1}f[j]\)

代码

#include<bits/stdc++.h>
using namespace std;
int n,k;
int a[200100];
int main()
{
	scanf("%d%d",&n,&k);
	a[0]=1;
	a[1]=1;
	for(int i=2;i<=n;i++) {
		for(int j=1;j<=min(k,i);j++) {
			a[i]=(a[i]+a[i-j])%100003;
		}
	}
	printf("%d\n",a[n]);
	return 0;
}