C++递推经典案例No.1——青蛙跳台问题

一只青蛙一次可以跳上1级台阶，也可以跳上2级台阶。求该青蛙跳上一个 n 级的台阶总共有多少种跳法。

这是一个经典的递归/动态规划的例题，代码部分并不难，关键是要理清思路。由于每次可以跳1个或者两个，所以跳到当前台阶的来源只有两种：下一个和下两个台阶。因此，来到当前台阶的方案数，其实是前两者方案数的和！以此类推，直到找到最下面两个台阶（0和1）即可解出答案。

此处，我们用二叉树的思想进行简单的理解：

如上图，直到找到0或1，才能达到本次递归的终点（0or1都对）。

 具体代码如下：

#include <iostream>
#include <vector>
using namespace std;


int main(int argc, char** argv) 
{
	int n=0;
	cin>>n;
	vector<int> V;
	V.push_back(1);
	V.push_back(1);
	//压入0和1对应的方案数作为递归终点 
	for(int i=2;i<=n;i++)
	{
		int temp=V[i-1]+V[i-2];
		//方案数等于前两项的和 
		V.push_back(temp);
	}
	cout<<V[n]<<endl;
	
	return 0;
}