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

我们现在考虑递推。

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

我们现在先推导 \(f(n)\)。

设 \(k = 3\)。

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

\(f(n) = f(n - 1) + f(n - 2) + \dots + f(n - k)/f(1)\)。

即为：\(f(n) = \sum_{i = n - k / i = 1}^{n} f(i)\)。

代码如下：

#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;
}