题目描述
有N级的台阶,你一开始在底部,每次可以向上迈最多K级台阶(最少1级),问到达第N级台阶有多少种不同方式。
输入输出格式
输入格式:
输入文件的仅包含两个正整数N,K。
输出格式:
输入文件stair.out仅包括1个正整数,为不同方式数,由于答案可能很大,你需要输出mod 100003后的结果。
输入输出样例
输入样例#1: 复制
5 2
输出样例#1: 复制
8
说明
对于20%的数据,有N ≤ 10, K ≤ 3;
对于40%的数据,有N ≤ 1000;
对于100%的数据,有N ≤ 100000,K ≤ 100。
题目分析:
递推很经典的题目(但我感觉仍然是动态规划),我们设f[i]为到i的路的种类,则我们只能由f[i-k],f[i-k+1]…….f[i-1]到达,k为步数。
所以得到递推式:f[i]+=f[i-j](i-j>0,1<=j<=k)
边界条件:f[0]=1
实现代码:
#include <bits/stdc++.h>
using namespace std;int n,i,m,j;int f[100005];
int main()
{cin>>n>>m;memset(f,0,sizeof(f));f[0]=1; //很重要的初始化for(i=1;i<=n;i++) //枚举楼梯{for(j=1;j<=m;j++) //枚举可能的步数if(i-j>=0) f[i]+=f[i-j];f[i]%=100003;}cout<<f[n];return 0;
}