台阶问题(递推)"/>
台阶问题(递推)
Description
有 N 级的台阶,你一开始在底部,每次可以向上迈最多 K 级台阶(最少 1 级),问到达第 N 级台阶有多少种不同方式。
Input
两个正整数N,K。
1 ≤ N ≤ 106, 1 ≤ K ≤ 20Output
一个正整数,为不同方式数,由于答案可能很大,你需要输出 ans mod 100003 后的结果。
Sample Input
5 2
Sample Output
8
Hint
N级台阶的情况可以由 N-K ~ N-1 这些台阶的情况得到
#include <bits/stdc++.h>
using namespace std;const int max_n = 100010;
int dp[max_n];void solve(int n, int k)
{for (int i = 1; i <= k; i++){dp[i] = 1;}for (int i = 2; i <= n; i++){for (int j = 1; j <= k && j <= i; j++){dp[i] = (dp[i] + dp[i - j]) % 100003;}}cout << dp[n];
}int main()
{int n, k;while (scanf("%d%d", &n, &k) != EOF){solve(n, k);}return 0;
}
#include <stdio.h>
#include <string.h>
#include <stdlib.h>
const int mod = 100003;
inline int max(int a, int b) { return a > b ? a : b; }
int n, k;
int ans[111111];int main()
{while (scanf("%d%d", &n, &k) != EOF){ans[0] = 1;for (int i = 1; i <= n; i++){ans[i] = 0;for (int j = max(0, i - k); j < i; j++)ans[i] = (ans[i] + ans[j]) % mod;}printf("%d\n", ans[n]);}return 0;
}
更多推荐
台阶问题(递推)
发布评论