洛谷【C++编程基础】递归函数初步专题解题报告-创新互联

题目描述
楼梯有n阶台阶,上楼可以一步上一阶,也可以一步上二阶。用递归的方法编一程序计算共有多少种不同的走法。（试用递归完成，会出现什么问题，如何解决）
输入格式
一个正整数n（n不超过90）
输出格式
一个整数，表示走法方案数。
输入输出样例
输入
4
输出
5

题目出处
我第一秒想到的是暴力……（造化低了）33分

#includeusing namespace std;

int n,cnt;

void f(int s){if(s==n){++cnt;
		return;
	}
	if(s>n)return;
	for(int i=1;i<=2;++i)
		f(s+i);
	return;
}

int main(){cin>>n;
	f(0);
	cout<

仔细对比数据，竟发现答案是斐波那契数列！！！
自制奇葩递归

#includeusing namespace std;

long long n,ans,vh[100];

void f(int s){if(s<3){if(s==2)cout<<3<cout<vh[0]=1;//这一行加上只是为了对比发现斐波那契，可删除
	vh[1]=1;
	vh[2]=2;
	cin>>n;
	f(3);
	return 0;
}

标程：

#includeusing namespace std; 

long long dp[110];//记忆化
long long f(long long n){if(dp[n])return dp[n];
	if(n<=2)return n;//注意这个地方与标准斐波那契不同（因为这一题第n个答案是第(n+1)个斐波那契数，忘记的同学可以向上翻翻T7，这里原是return 1）
	else dp[n]=f(n-1)+f(n-2);
	return dp[n];
}

int main(){int n;
	cin>>n;
	cout<

刨根问底的同学可以继续看：
QUESTION:为什么答案是斐波那契数列？
ANSWER:上面我们用的是归纳的方法。下面主要介绍原因：
第1,2个台阶分别有1,2种走法（1）（1+1或2）
而从第3个开始，每一个数目（假设是第n个（n>2））都可以理解为第(n-1)的走法再走1级台阶或第(n-2)的走法再走2级台阶，自然就有第(n-1)，第(n-2)的走法总数和数量的方法。