【面试题】拿球游戏的得分期望

题目

袋子里有10个红球和10个黑球，游戏规则是：拿到红球得1分，拿到黑球减1分，进行无放回拿20次，当你发现继续拿球不利于得分时，可以提前终止比赛，请计算得分的期望。

解答

为了计算得分的期望，我们可以使用动态规划（Dynamic Programming）的方法。我们定义一个三维数组dp[i][j][k]表示在剩余i个红球、j个黑球和剩余k次抽取机会时的期望得分。我们的目标是计算dp[10][10][20]。

python代码

def expected_score():
    dp = [[[0 for _ in range(21)] for _ in range(11)] for _ in range(11)]

    for k in range(1, 21):
        for i in range(11):
            for j in range(11):
                if i == 0 and j == 0:
                    continue
                total_balls = i + j
                prob_red = i / total_balls
                prob_black = j / total_balls
                expected_if_continue = prob_red * (1 + dp[i - 1][j][k - 1]) + prob_black * (-1 + dp[i][j - 1][k - 1])
                if expected_if_continue > 0:
                    dp[i][j][k] = expected_if_continue
                else:
                    dp[i][j][k] = 0

    return dp[10][10][20]

print(expected_score())