题目描述
有 NN 级的台阶，你一开始在底部，每次可以向上迈最多 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 。
我的做法：- #include<iostream>
- #include<cstdio>
- using namespace std;
- int main()
- {
- int s[100002]= {0},n,k;
- scanf("%d%d",&n,&k);
- s[0]=1;
- for(int i=1; i<=n; i++)
- {
- for(int j=1; j<=k && (i-j)>=0; j++)
- s[i]+=s[i-j];
- s[i]=s[i]%100003;
- }
- printf("%d",s[n]);
- return 0;
- }
|
|