for(int i=1;i<(1<<n);i++)
{
	for(int j=1;j;j=i&(j-1))
	{
		g[i]=max(g[i],g[j]+1);
	}
}

答案上说是 $O(3^n)$，不知道为什么。