猴子爬山问题

问题: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;
}

猴子爬山问题

原文：http://blog.csdn.net/lc0817/article/details/44593287