数楼梯

题源:
https://www.acwing.com/problem/content/823/

题目描述

楼梯有 N 阶，上楼可以一步上一阶，也可以一步上二阶。

编一个程序，计算共有多少种不同的走法。

输入格式

一个数字，楼梯数。

输出格式

输出走的方式总数。

样例

样例输入

4

样例输出

5

---

好像是挺经典一道题，哪个网站的题库都有。
考虑到用某个方案走上来后，最后一步都会是上一阶或两阶楼梯，那么如果用f(x)表示上了x阶台阶的总方案数，我们就可以列出这样一个表达式：f(x) = f(x - 1) + f(x - 2) 它表示总方案数等于最后一步上了一阶的方案数和最后一步上了两阶的方案数的和。同样的，如果f(x - 1)表示上了n - 1阶的总方案数，它也可以拆分为两个方案的和：f(x - 1) = f(x - 1 - 1) + f(x - 1 - 2) ，f(x - 2)同理，并且可以继续一直拆分。如此我们发现这里是一个递归的关系，并且我们知道最开始两种的方案数f(1) = 1,f(2) = 2。写一个递归函数，打印出结果就好。

#include<stdio.h>
int f(int x)
{
	int fx;
	if (x == 1)
	{
		return 1;
	}
	if (x == 2)
	{
		return 2;
	}
	else
	{
		fx = f(x - 1) + f(x - 2);
		return fx;
	}
}
int main()
{
	int N;
	int res;
	scanf("%d", &N);
	res = f(N);
	printf("%d", res);
	return 0;
}