计蒜客 爬楼梯

今天做的是一道动态规划的题目，从最简单的做起，本人现在都比较喜欢在计蒜客上面做题目

假设你现在正在爬楼梯，楼梯有n级。每次你只能爬1级或者2级，那么你有多少种方法爬到楼梯的顶部？

输入格式

第一行输入一个整数n(1≤n≤50)，代表楼梯的级数。

输出格式

输出爬到楼梯顶部的方法总数。

样例输入

5

样例输出

8

解析

这个题目很简单，一共有n级楼梯，我们从先上往下看，要爬到n，起码要爬到n-1然后再爬1级或者爬到n-2再爬2级。意思就是爬到第n级的方法总数等于爬到n-1级的方法总数加爬到n-2级的方法总数。

即F(n)=F(n-1)+F(n-2)  已知条件F(1)=1  F(2)=2

然而这是一种递归的思路自顶向下，动态规划的思路自底向上

从已知的F(1) F(2)推出F(3)，再推出F(4)...以此类推

代码

int d[55]={0};

int main()

{

d[0]=1;

d[1]=1;

d[2]=2;

int n=0;

scanf("%d",&n);

for(int i=3;i<=n;i++)

{

d[i]=d[i-2]+d[i-1];

}

printf("%d\n",d[n]);

return 0;

}