难度：普及-

题目类型：递推

提交次数：1

涉及知识：递推

题目描述

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

输入输出格式

输入格式：

输入文件的仅包含两个正整数N，K。

输出格式：

输入文件stair.out仅包括1个正整数，为不同方式数，由于答案可能很大，你需要输出mod 100003后的结果。

代码：

 1 #include<iostream> 2 using namespace std; 3 int n, k; 4 int a[100001]; 5 int main(){ 6     cin>>n>>k; 7     int i, j; 8     a[0] = 1; 9     for(i = 1; i <= n; i++){10         for(j = 1; j <= i&&j <= k; j++)11             a[i] = (a[i]+a[i-j])%100003;12        // a[i]%=100003;13     }14     cout<<a[n];15     return 0;16 }

备注：

设f(n)为还剩n层时的不同方式数，递推方程为f(n) % p= [f(n-1)+f(n-2)+……+f(n-k)] % p, 即当前走1步——走k步的方案数的总和。

还有取模运算，(a + b) % p = (a % p + b % p) % p

我发现注释掉那行加不加都可以。完了，取模运算搞得我好茫然。。

靠，我想不明白，不想了！

1192 台阶问题