洛谷 1192:台阶问题(递推,DP)

时间:2022-12-26 17:08:57

题目描述

有 N 级的台阶,你一开始在底部,每次可以向上迈最多 K 级台阶(最少 1 级),问到达第 N 级台阶有多少种不同方式。

输入输出格式

输入格式:

两个正整数N,K。

输出格式:

一个正整数,为不同方式数,由于答案可能很大,你需要输出 ans mod 100003 后的结果。

输入输出样例

输入样例#1:

5 2

输出样例#1:

8

说明

对于 20% 的数据,有 N ≤ 10, K ≤ 3;

对于 40% 的数据,有 N ≤ 1000;

对于 100% 的数据,有 N ≤ 100000,K ≤ 100。

洛谷 1192:台阶问题(递推,DP)

思路

每次上台阶时肯定都是一次走上去,那么就看上次所在台阶的位置。假如说一次上四个台阶,上到第50层。那么到第五十层的步数为在第49,48,47,46,45这些方案数相加。

写一个递推关系就好了:a[n]=a[n-1]+a[n-2]+……+a[n-k] 。对于到达每一层都是这样的方法,一直算下去就好了。注意要每次取模

AC代码

#include <stdio.h>
#include <string.h>
#include <iostream>
#include <algorithm>
#include <math.h>
#include <limits.h>
#include <map>
#include <stack>
#include <queue>
#include <vector>
#include <set>
#include <string>
#define ll long long
#define ms(a) memset(a,0,sizeof(a))
#define pi acos(-1.0)
#define INF 0x3f3f3f3f
const double E=exp(1);
const int maxn=1e6+10;
const int mod=100003;
using namespace std;
int a[maxn];
int main(int argc, char const *argv[])
{
ios::sync_with_stdio(false);
int n,k;
cin>>n>>k;
ms(a);
a[0]=1;
for(int i=1;i<=n;i++)
{
for(int j=1;j<=k&&j<=i;j++)
a[i]=(a[i]%mod+a[i-j]%mod)%mod;
}
cout<<a[n]%mod<<endl;
return 0;
}