d038: 00900 - Brick Wall Patterns

解題心得

這題的本質就是 fib ，原因是要找 n 能有幾種拼法，就是把 n-1 的所有方法再加上直立的一個磚塊，以及 n-2 的所有方法再加上兩個平躺磚塊。

網路上的解法比較多是事先建表。我的寫法是每次都會查表，而若以前做過就不會重做。

程式碼

#include <iostream>
using namespace std;

long long int memo[51] = { 0 };
long long int f(int n)
{
	if (memo[n] != 0) return memo[n];
	if (n <= 2) return n;
	memo[n] = f(n - 1) + f(n - 2);
	return memo[n];
}
int main()
{
	int n;
	while (cin >> n)
	{
		if (n == 0) break;
		cout << f(n) << endl;
	}
	return 0;
}