递推配套P1192 and 题解：P1192 台阶问题

我们现在考虑递推。

现在的问题是，如何从前几个数据推导出下一个数据。

我们现在先推导 。

设 。

到 的方法就是到能一步到 的台阶的方法总和，所以我们可以推导出：

。

即为：。

代码如下：

#include <bits/stdc++.h>
using namespace std;
int n, k, a[100005];
int main()
{
    cin >> n >> k;
    a[0] = 1;
    a[1] = 1;
    for (int i = 2; i <= n; i++)
    {
        for (int j = i - 1; j >= 0 && j >= i - k; j--)
            a[i] += a[j], a[i] %= 100003;
    }
    cout << a[n] << endl;
    return 0;
}