luogu P1192【台阶问题】

#include<iostream>
#include<cstdio>
using namespace std;
#define MAX 100005
#define mod 100003
int n,k;
int bin[MAX];
int f(int i){
	if(i==0)return 1;//当i为0时返回1
	if(bin[i])return bin[i]%mod;//如果在做这个的时候f(i)已经被推出来了，就直接调用bin[i]
	for(int j=1;j<=k&&i-j>=0;++j)bin[i]=(bin[i]%mod+f(i-j)%mod)%mod;//没有就做一遍
	return bin[i]%mod;
}
int main(){
	scanf("%d%d",&n,&k);
	printf("%d\n",f(n)%mod);//注意最后也要%一下
	return 0;
}

#include<iostream>
#include<cstdio>
using namespace std;
#define MAX 100005
#define mod 100003
int n,k;
int bin[MAX];
int f(int i){
	if(i==0)return 1;
	if(bin[i])return bin[i]%mod;
	for(int j=1;j<=k&&i-j>=0;++j)bin[i]=(bin[i]%mod+f(i-j)%mod)%mod;
	return bin[i]%mod;
}
int main(){
	scanf("%d%d",&n,&k);
	printf("%d\n",f(n)%mod);
	return 0;
}