n次抛硬币游戏获胜概率计算：优化暴力算法支持大n值
硬币被抛掷n次：当连续抛出两次正面（Heads）时，玩家1（Alice）得1分；当抛出正面后接反面（Tails）时，玩家2（Bob）得1分。
例如，在序列"HTTTHHHT"中，Alice从"HHH"子串获得2分，Bob从"HT"子串获得2分，最终结果为平局。
我实现了一个暴力算法来计算各玩家获胜或平局的概率，但该算法无法处理大n值。由于n次抛掷共有2n种排列，当2n超出整数限制时程序会失效；即使能处理更大数值，计算大n值的耗时也极长。如何开发一种无需生成所有排列的更优算法？
以下是我当前的算法（假设正面为0，反面为1，Alice对应HH，Bob对应HT）：
public class Probability { public static void main(String[] args) { int n = 5; int[] winners = Permutations(n); float pA = winners[0] / (float) (1 << n); float pB = winners[1] / (float) (1 << n); float pT = winners[2] / (float) (1 << n); System.out.printf("%d Tosses. P(Alice): %.3f. P(Bob): %.3f. P(Tie): %.3f\n", n, pA, pB, pT); } public static int[] Permutations(int n) { int amtPerm = 1 << n; // How many permutations to generate int[] perm = new int[n]; // Fills with all 0 by default int[] winners = {1, 0, 0}; // Alice, Bob, Tie (Counted the first permutation of all 0s as an Alice win) for(int i = 1; i < amtPerm; i++) { int j = n-1; while(true) { if(perm[j] == 0) { perm[j++] = 1; for(; j < n; j++) { // set all values after j to 0 perm[j] = 0; } break; } else { j--; } } // Traverse the new permutation to determine a winner int alice = 0, bob = 0; for(int k = 1; k < n; k++) { if(perm[k-1] == 0 && perm[k] == 0) alice++; else if(perm[k-1] == 0 && perm[k] == 1) bob++; } if(alice > bob) winners[0] += 1; else if(bob > alice) winners[1] += 1; else winners[2] += 1; } return winners; } }
该算法在小n值下表现正常，但无法支持大n值计算。比如输入n=1000时，会得到错误的结果："P(Alice): 1.000, P(Bob): 0.000, P(Tie): 0.000"。
暴力枚举所有排列的复杂度是O(2^n)，完全无法处理n≥30的情况。我们可以用动态规划跟踪状态和得分差的概率，将复杂度降到O(n)，轻松支持n=1000甚至更大的数值。
核心思路
我们只需要跟踪两个关键信息：
- 最后一次抛掷的结果（正面/反面）——下一次抛掷是否产生得分完全取决于上一次的结果
- 当前Alice与Bob的得分差（Alice得分 - Bob得分）——直接决定最终胜负
状态定义
定义dp[k][s][last]为抛掷k次后，得分差为s，最后一次抛掷结果为last（0=正面，1=反面）的概率：
k：已抛掷次数，范围1到ns：得分差，范围从-(k-1)到+(k-1)（k次抛掷最多有k-1个连续对，每次最多改变1分）last：0或1，代表最后一次抛掷结果
初始状态
当k=1时，没有连续对，得分差为0：
dp[1][0][0] = 0.5（第一次抛正面的概率）dp[1][0][1] = 0.5（第一次抛反面的概率）
状态转移
对于k>1的情况，分两种情况处理：
- 上一次最后是正面（last=0）：
- 本次抛正面：出现HH，Alice得1分，得分差+1 →
dp[k][s+1][0] += dp[k-1][s][0] * 0.5 - 本次抛反面：出现HT，Bob得1分，得分差-1 →
dp[k][s-1][1] += dp[k-1][s][0] * 0.5
- 本次抛正面：出现HH，Alice得1分，得分差+1 →
- 上一次最后是反面（last=1）：
- 本次抛正面：出现TH，无得分，得分差不变 →
dp[k][s][0] += dp[k-1][s][1] * 0.5 - 本次抛反面：出现TT，无得分，得分差不变 →
dp[k][s][1] += dp[k-1][s][1] * 0.5
- 本次抛正面：出现TH，无得分，得分差不变 →
空间优化
因为计算k次的状态只需要k-1次的状态，我们可以用两个字典（或数组）分别存储当前状态和上一状态，避免使用三维数组浪费空间。对于n=1000，得分差的范围是-999到999，总共1999个可能值，空间占用极小。
最终概率计算
遍历n次抛掷后的所有状态：
- Alice获胜概率：所有
s>0的dp[n][s][0] + dp[n][s][1]之和 - Bob获胜概率：所有
s<0的dp[n][s][0] + dp[n][s][1]之和 - 平局概率：
dp[n][0][0] + dp[n][0][1]
示例伪代码
def calculate_probabilities(n): # 初始化上一状态：k=1时，得分差0，last0和last1的概率都是0.5 prev = {} prev[(0, 0)] = 0.5 # (得分差, last) -> 概率 prev[(0, 1)] = 0.5 for k in range(2, n+1): curr = {} for (s, last), prob in prev.items(): if last == 0: # 抛正面，得分+1 key = (s+1, 0) curr[key] = curr.get(key, 0) + prob * 0.5 # 抛反面，得分-1 key = (s-1, 1) curr[key] = curr.get(key, 0) + prob * 0.5 else: # 抛正面，得分不变 key = (s, 0) curr[key] = curr.get(key, 0) + prob * 0.5 # 抛反面，得分不变 key = (s, 1) curr[key] = curr.get(key, 0) + prob * 0.5 prev = curr p_alice = 0.0 p_bob = 0.0 p_tie = 0.0 for (s, _), prob in prev.items(): if s > 0: p_alice += prob elif s < 0: p_bob += prob else: p_tie += prob return p_alice, p_bob, p_tie
这个方法无需生成任何排列，通过状态转移直接计算概率，时间和空间复杂度均为O(n)，即使n=1000也能快速得到准确结果。
内容的提问来源于stack exchange，提问作者Peterfvn
