台阶问题

题目描述

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

输入格式

两个正整数 $N,K$。

输出格式

一个正整数 $ans(\mathrm{mod}100003)$，为到达第 $N$ 级台阶的不同方式数。

样例 #1

样例输入 #1

5 2

样例输出 #1

8

提示

• 对于 $20\%$ 的数据，$1\le N\le 10$，$1\le K\le 3$；
• 对于 $40\%$ 的数据，$1\le N\le 1000$；
• 对于 $100\%$ 的数据，$1\le N\le 100000$，$1\le K\le 100$。

解题思路

• 动态规划。
• 状态转移方程：dp[i] = dp[i] + dp[i - j]；i表示当前的台阶数，j表示每次可以达到的最大台阶数。
• 状态初始化：dp[0] = 1。

Code

#include<iostream>
#include <vector>

using namespace std;

int num = 100003;
int n, k;
vector<int> dp(100000); // 定义数组

int main() {
	cin >> n >> k;  // 输入数据
	dp[0] = 1;
	for (int i = 0; i <= n; i++) {
		for (int j = 1; j <= k; j++) {
			if (i >= j) {
				dp[i] = (dp[i] + dp[i - j]) % num;
			}
		}
	}
	cout << dp[n] << endl;
	return 0;
}

运行结果