假设每一步可以爬一格或者两格梯子,爬一部n格梯子一共可以用几种不同的方法?

假设n格梯子有f(n)种方法。
则：
f(1) = 1
f(2) = 2
对n>2，有：
f(n) = （先上一格，再上n-1格的方法数） + （先上两格，再上n-2格的方法数）
即
f(n) = f(n-1) + f(n-2)

所以f(n)是Fibonacci数列的第n+1项？
#include
long fib(int n)
{ if (n == 1 || n == 2) return 1;
return fib(n - 1) + fib(n - 2);
}
main()
{ int n;
scanf("%d", &n);
printf("%ld\n", fib(n+1));
return 0;
}

/*
习题 9：上阶梯★★

上阶梯，你可以一个一个阶梯上，也可以两个两个地来，
也可以一个和二个间隔着上，甚至可以一次k个阶梯
问题是，上一个阶梯数为n，每步能上1至k个阶的话，
你有多少种方法走完它？

如 n = 5 , k = 2，可以
1,1,1,1,1
2,1,1,1
1,2,1,1
1,1,2,1
1,1,1,2
2,2,1
2,1,2
1,2,2
共8种

输入阶梯数n(1 <= n <= 30)和每步最大阶数k(1<=k<=n)：
5 2
5 3

输出：
8
13

难度：Easy
*/
#include
#include
int d[31][31];
int dfs(int left,int k)
{
int i;
if(d[left][k]!=-1) return d[left][k];
if(!left) return 1;
d[left][k]=0;
for(i=1;i<=((left d[left][k]+=dfs(left-i,k);
return d[left][k];
}
int main(void)
{
int n,k;
memset(d,-1,sizeof(d));
while(scanf("%d%d",&n,&k)!=EOF)
printf("%d\n",dfs(n,k));
return 0;
}