C语言编程练习16：统计方案

2
1
2

3
7
思路：我自己还是没找出来，画画图然后参考了其他大佬的博客
大佬解析1（感觉这个最好理解）：因为n+1时都可以往两个方向或者三个方向；三个方向是为n时向上的状态；为n时有多少个向上的状态？当n-1有多少状态，n就有多少个向上的状态；所以递推公式为a[n]=2*a[n-1]+a[n-2];
大佬解析2：赤裸裸的递推问题，设第n步的走法为F(n)，往上走的步数为a(n),往左或往右走的步数为b(n)；

所以F(n)=a(n)+b(n);接下来分别找前一个状态。因为不能往下走，所以向上走的步数只有一种选择就是上一次的步数相加：a(n)=a(n-1)+b(n-1)（前（n-1）步内往上走的步数+前（n-1）步内往左或右的步数）;又因为走过的不能返回，所以往左或右走只有一种方法，但向上走可以是左上和右上两种，因此b(n)=2*a(n-1)+b(n-1);化简得F(n)=2*F(n-1)+F(n-2);

#include <stdio.h>
#include <iostream>
#include <cstring>

using namespace std;

int f(int x)
{
	if(x==0)
	{
		return 1;
	}
	if(x==1)
	{
		return 3;
	}
	return 2*f(x-1)+f(x-2);
}
int main()
{
	int n;
	cin >> n;
	while(n--)
	{
		int m;
		cin >> m;
		cout << f(m) <<endl;
			
	}
    return 0;
}