算法：骨牌铺方格(递推)
Description
在2×n的一个长方形方格中,用一个1× 2的骨牌铺满方格,输入n ,输出铺放方案的总数. 例如n=3时,为2× 3方格，骨牌的铺放方案有三种,如下图：
Input
输入数据由多行组成，每行包含一个整数n,表示该测试实例的长方形方格的规格是2×n (0< n<=50)。
Output
对于每个测试实例，请输出铺放方案的总数，每个实例的输出占一行。
Sample Input
1 3 2
Sample Output
1 3 2
HINT
此题用long long 类型
思路：
n = 0时，不能没有块可以填充，f(0) = 0;
n = 1时，只能竖着填充一块，f(1) = 1;
n = 2时，可以竖着两块，横着两块，f(2) = 2。
n = 3时，可以当成先选了一块竖着的，然后f(3 - 1) = f(2)，或者先选两块横着的，然后f(3 - 2) = f(1)，
所以f(3) = f(3 - 1) + f(3 - 2) = f(2) + f(1) = 3;
f ( n ) = f ( n − 1 ) + f ( n − 2 ) , n > 2 f(n) = f(n - 1) + f(n - 2), n >2 f(n)=f(n−1)+f(n−2), n>2
AC代码：
#include <iostream>
using namespace std;
int main()
{
ios::sync_with_stdio(false);
cin.tie(NULL);
cout.tie(NULL);
long long f[51] = {
0, 1, 2};
for (int i = 3; i < 51; i++)
f[i] = f[i - 1] + f[i - 2];
int n;
while (cin >> n)
cout << f[n] << endl;
return 0;
}
下一篇：
数学建模常考三大模型