papamelon 352. 计算铺设方法的个数（算法问题实战策略）

地址 https://www.papamelon.com/problem/352

解答
由于已经确定是2排待填充的地板，那么填充方法就是两种
如图

又已知待填充的地板长度为n，题意可以转换为 要么选择1个竖方案填充要么选择2个横方案 ，问有达到长度n有多少种选择。
再推断一步 使用1代替1个竖砖块方案，使用2代替2个横砖块方案， 请问仅使用连续的1和2，有多少种排列可以刚好达到和为n

n=1的时候 只有1中答案 1
n=2的时候 有两种答案 11 2
n=3的时候 有3种答案 111 12 21
n=4的时候 有5种答案 22 211 112 121 1111
n=5的时候 有8种答案

以上 这就是一个斐波那契数列，所以代码如下

#include <iostream>

using namespace std;

int dp[150];

int main()
{
	dp[1] = 1; dp[2] = 2;

	for (int i = 3; i <= 101; i++) {
		dp[i] = dp[i - 1] + dp[i - 2];
		dp[i] %= 1000000007;
	}

	int n;
	cin >> n;
	while (n--) {
		int a;
		cin >> a;
		cout << dp[a] << endl;

	}
	return 0;
}

我的视频题解空间