Twitter電面

A, B兩人 play ping-pong, A 得分的機率是P

您好！
本帖隐藏的内容需要积分高于 188 才可浏览
您当前积分为 0。
使用VIP即刻解锁阅读权限或查看其他获取积分的方式

游客，您好！
本帖隐藏的内容需要积分高于 188 才可浏览
您当前积分为 0。
VIP即刻解锁阅读权限 或 查看其他获取积分的方式
Unlock interview details and practice with AI
Curated Interview Questions from Top Companies

推，請問A獲勝的機率是多少?

您好！
本帖隐藏的内容需要积分高于 100 才可浏览
您当前积分为 0。
使用VIP即刻解锁阅读权限或查看其他获取积分的方式

游客，您好！
本帖隐藏的内容需要积分高于 100 才可浏览
您当前积分为 0。
VIP即刻解锁阅读权限 或 查看其他获取积分的方式
Unlock interview details and practice with AI
Curated Interview Questions from Top Companies

请问这题是该如何入手？完全没有思路。。orz

感觉可以用两维DP来解：（假设没有得0分的时候）
DP[a][b]等于A得a分同时B得b分的概率。这样算到最后ans = DP[11][0] + DP[11][1] + ... + DP[11][10]。
时间复杂度是21 * (11 * 11)。
如果有的0分的时候，那么此题无解……他们俩有概率打一辈子……

“A 得分的機率是Pa, B得分的機率是Pb” 这个应该是谁先serve ball吧，否则 Pa + Pb = 1
感觉至少brute force是dps进去，直到得分是11分截止，所有path的probability加在一起
优化应该是dp，dp[a][b] = dp[a][b-1] * p(谁发球) + dp[a-1][b] * p(谁发球)