动态规划、组合数学

Solution 1：设计 $dp_{i,j}$ 为剩余 $i$ 张 A 类票和 $j$ 张 B 类票的概率，边界条件 $dp_{n,n}=1$，状态转移方程 $dp_{i,j}=0.5 \times (dp_{i+1,j} + dp_{i,j+1})$，记忆化搜索。答案为 $dp_{2,0}+dp_{0,2}$，时间复杂度 $O(n^2)$。

Solution 2：容斥计算剩余一张 A 类票和一张 B 类票的概率 $P$。保护一张 A 类票和一张 B 类票，此时剩余 $2n-2$ 张票。

取走剩下 $2n-2$ 张票的方案数为 $C_{2n-2}^{n-1}$，每种取票情况出现的概率为 $\left( \dfrac{1}{2} \right)^{2n-2}$。有 $P=C_{2n-2}^{n-1} \times \left( \dfrac{1}{2} \right)^{2n-2}=\dfrac{\prod\limits_{i=n}^{2n-2} i}{\prod\limits_{i=1}^{n-1} 4i}$。答案为 $1-P$，时间复杂度 $O(n)$。