d887: 1.山脈種類(chain)

解題心得

連續寫了幾題，對怎麼分析好像稍微有點感覺了。雖然還是不會寫。

DP的精神就是切割成小問題，這題的切法是想：曲線第一次的落地點在哪？

山的總長度為2n，因此落地可在2n, 2n-2, 2n-4, ......, 0。

程式碼

#include <iostream>
using namespace std;

int main()
{
	long long int memo[26] = { 1,0 }, n;
	for (int i = 1; i < 26; i++)
	{
		for (int j = 0; j < i; j++)
			memo[i] += memo[j] * memo[i - 1 - j];
	}
	while (cin >> n)
	{
		cout << memo[n] << endl;
	}
	return 0;
}