洛谷P1192 台阶问题——简单的递推
Solution:
这是一道简单的递推题目,每一节台阶都要从前面的台阶上来,因为每次可以上1~k阶台阶,所以我们假设要上第n阶台阶(n>=k),那么就可以从第0
~n-k阶台阶上来。于是可以写出递推式steps[n]=steps[n]+steps[n-k]。
代码如下:
#include<iostream>
#define MAX 100005
using namespace std;
int steps[MAX];
int n,k;
int main(){
cin>>n>>k;
for(int i=0;i<MAX;i++){//初始化数组
steps[i]=0;
}
steps[0]=1;
for(int i=1;i<=n;i++){
for(int j=1;j<=k&&(i-j)>=0;j++){
steps[i]=steps[i]+steps[i-j];
steps[i]=steps[i]%100003;
}
}
cout<<steps[n];
return 0;
}