网站怎么做发送邮件的超链接/搜索引擎优化的目的是对用户友好

问题:n级的台阶,每次可以跨一步,有m种跨法,求爬到第n阶台阶,共有多少种不同的爬法?

例: 一个猴子在一座30级台阶的山上爬山,猴子上山一步可跳1级,或3级,试求上山的30级台阶有多少种不同爬法

input:

30 2

1

3

output:

58425

input:

50 4

2

3

5

6

output:

106479771

#include<iostream>
using namespace std;
int main()
{int i,j,k,n,m,stage[100]={0},step[100];cin>>n>>m;for(i=0;i<m;i++){cin>>step[i];//需从小到大输入跨步方法 stage[step[i]]=1;//eg: step[0]=3,stage[3]=1 意味着第0种跨法(每次跨3级)可以一步跨到第stage[step[0]]级台阶上   }step[m]=n; //以n作为第m+1种跨法,方便计算 /*过程:1.从stage[1]到stage[step[0]]  stage都为0,因为最小的跨步方法是step[0].2.从stage[step[0]+1]到stage[step[1]]  有 stage[x]=stage[x]+stage[x-step[0]](step[0]<x<=step[1]) 3.从stage[step[1]+1]到stage[step[2]]  有 stage[x]=stage[x]+stage[x-step[0]]+stage[x-step[1]](step[1]<x<=step[2])4.以此类推 */for(i=0;i<m;i++) for(j=step[i]+1;j<=step[i+1];j++)for(k=0;k<=i;k++)stage[j]+=stage[j-step[k]];cout<<stage[n]<<endl;return 0;
}