台阶问题额

题目名字

台阶问题

题意

1. 初始化数组f的第一个元素为1。这表示到达第0级台阶的方式数为1，即不需要迈任何台阶。
2. 从第1级台阶开始，迭代计算每一级台阶的不同方式数。
3. 对于当前台阶i，内部循环从1到i和k中的较小值开始迭代。这是因为每次只能向上迈1到k级台阶，所以我们只需要考虑当前台阶i和最大可迈级数k之间的较小值。
4. 计算到达第i级台阶的不同方式数。对于当前台阶i，我们将其不同方式数初始化为0，然后通过累加之前的台阶（i-j）的不同方式数来计算到达第i级台阶的不同方式数。最后对结果取模100003，以防止整数溢出。
5. 输出到达第n级台阶的不同方式数。

思路

1. 初始化数组f的第一个元素为1。这表示到达第0级台阶的方式数为1，即不需要迈任何台阶。
2. 从第1级台阶开始，迭代计算每一级台阶的不同方式数。
3. 对于当前台阶i，内部循环从1到i和k中的较小值开始迭代。这是因为每次只能向上迈1到k级台阶，所以我们只需要考虑当前台阶i和最大可迈级数k之间的较小值。
4. 计算到达第i级台阶的不同方式数。对于当前台阶i，我们将其不同方式数初始化为0，然后通过累加之前的台阶（i-j）的不同方式数来计算到达第i级台阶的不同方式数。最后对结果取模100003，以防止整数溢出。
5. 输出到达第n级台阶的不同方式数。

坑点

1. 先要有初始化步骤

算法一：递推

实现步骤

1. 初始化数组f的第一个元素为1。这表示到达第0级台阶的方式数为1，即不需要迈任何台阶。
2. 从第1级台阶开始，迭代计算每一级台阶的不同方式数。
3. 对于当前台阶i，内部循环从1到i和k中的较小值开始迭代。这是因为每次只能向上迈1到k级台阶，所以我们只需要考虑当前台阶i和最大可迈级数k之间的较小值。
4. 计算到达第i级台阶的不同方式数。对于当前台阶i，我们将其不同方式数初始化为0，然后通过累加之前的台阶（i-j）的不同方式数来计算到达第i级台阶的不同方式数。最后对结果取模100003，以防止整数溢出。
5. 输出到达第n级台阶的不同方式数。

代码

#include<iostream>
using namespace std;
int f[100005],n,k;
int main()
{
	cin>>n>>k;
	f[0]=1;
	for(int i=1;i<=n;i++)
	{
		for(int j=1;j<=min(i,k);j++)
			f[i]=(f[i]+f[i-j])%100003;
	}
	cout<<f[n];
	return 0;
}