题目描述
有 N 级的台阶，你一开始在底部，每次可以向上迈最多 K 级台阶（最少 1 级），问到达第 N 级台阶有多少种不同方式。
输入输出格式
输入格式：
两个正整数N，K。
输出格式：
一个正整数，为不同方式数，由于答案可能很大，你需要输出 ans mod 100003 后的结果。
输入输出样例
输入样例#1：
5 2输出样例#1：
8说明
对于 20% 的数据,有 N ≤ 10, K ≤ 3;
对于 40% 的数据，有 N ≤ 1000;
对于 100% 的数据，有 N ≤ 100000,K ≤ 100。
思路
每次上台阶时肯定都是一次走上去，那么就看上次所在台阶的位置。假如说一次上四个台阶，上到第50层。那么到第五十层的步数为在第49，48,47,46,45这些方案数相加。
写一个递推关系就好了：a[n]=a[n-1]+a[n-2]+……+a[n-k] 。对于到达每一层都是这样的方法，一直算下去就好了。注意要每次取模
AC代码
#include <stdio.h>
#include <string.h>
#include <iostream>
#include <algorithm>
#include <math.h>
#include <limits.h>
#include <map>
#include <stack>
#include <queue>
#include <vector>
#include <set>
#include <string>
#define ll long long
#define ms(a) memset(a,0,sizeof(a))
#define pi acos(-1.0)
#define INF 0x3f3f3f3f
const double E=exp(1);
const int maxn=1e6+10;
const int mod=100003;
using namespace std;
int a[maxn];
int main(int argc, char const *argv[])
{
ios::sync_with_stdio(false);
int n,k;
cin>>n>>k;
ms(a);
a[0]=1;
for(int i=1;i<=n;i++)
{
for(int j=1;j<=k&&j<=i;j++)
a[i]=(a[i]%mod+a[i-j]%mod)%mod;
}
cout<<a[n]%mod<<endl;
return 0;
}