UVA 580 - Critical Mass（DP）

#include <stdio.h>
#include <string.h>

int n, dp[32][4][2];

int dfs(int num, int s, int flag) {
	int &ans = dp[num][s][flag];
	if (ans != -1) return ans;
	ans = 0;
	if (num == n) {
		if (flag) ans = 1;
		return ans;
	}
	int ss = ((s&1)<<1);
	if (flag == 1)	
		ans = dfs(num + 1, ss|1 , 1) + dfs(num + 1, ss, 1);
	else
		ans = dfs(num + 1, ss|1, s == 3) + dfs(num + 1, ss, 0);
	return ans;
}

int main() {
	while (~scanf("%d", &n) && n) {
		memset(dp, -1, sizeof(dp));
		printf("%d\n", dfs(0, 0, 0));
	}
	return 0;
}