UVA 10312 - Expression Bracketing（數論+Catalan數）

題目鏈接：10312 - Expression Bracketing

題意：有n個x，要求分括號，判斷非二叉表達式的個數。 思路：二叉表達式的計算方法就等於是Catalan數的，那麼只要計算出總數，用總數減去二叉表達式個數，得到的就是非二叉表達式的個數。那麼計算方法是什麼呢。 看題目中的圖，對於n = 4的情況，可以分為這幾種情況來討論： 四個1， 一個2兩個1，一個3一個1，一個4，對應的情況數為1，3， 2， 1。 答案為f(1)^4 + 3 * f(2) * f(1)^2 + f(3) * f(1) + f(4)。 一種做法是把n去分解然後計算，但是顯然這是不可行的，n最大為26，情況數太多了。 然後找題解，發現這個居然有公式，這個式子叫SuperCatalan數。

然後也有遞推出來的解，設dp[n][2]，n表示還有n個子節點未分配，2表示0為最多分配n - 1個點，1為最多分配n個點，這樣能保證子樹都至少有兩個節點，這樣就是總情況了，直接用記憶化搜下去即可

代碼：

公式解：

#include 
#include 

int n;
long long Catalan[30], SuperCatalan[30];

int main() {
	Catalan[1] = Catalan[2] = 1;
	for (int i = 3; i <= 26; i++) {
		Catalan[i] = Catalan[i - 1] * (4 * i - 6) / i;
 	}
 	SuperCatalan[1] = SuperCatalan[2] = 1;
 	for (int i = 3; i <= 26; i++) {
		SuperCatalan[i] = (3 * (2 * i - 3) * SuperCatalan[i - 1] - (i - 3) * SuperCatalan[i - 2]) / i;
	}
	while (~scanf("%d", &n)) {
		printf("%lld\n", SuperCatalan[n] - Catalan[n]);
 	}
	return 0;
}

遞推解：

#include 
#include 

int n;
long long Catalan[30], dp[30][2];

long long dfs(int n, int flag) {
	long long &ans = dp[n][flag];
	if (~ans) return ans;
	if (n <= 1) return ans = 1;
	ans = 0;
	for (int i = 1; i < n + flag; i++)
		ans += dfs(i, 0) *	dfs(n - i, 1);
	return ans;
}

int main() {
	Catalan[1] = Catalan[2] = 1;
	for (int i = 3; i <= 26; i++) {
		Catalan[i] = Catalan[i - 1] * (4 * i - 6) / i;
 	}
	while (~scanf("%d", &n)) {
		memset(dp, -1, sizeof(dp));
		printf("%lld\n", dfs(n, 0) - Catalan[n]);
 	}
	return 0;
}