算法设计,老师给的题,9-1在一次世界系列赛中有A和B两支队伍,整个系列算法设计,老师给的题,9-1在一次世界系列赛中有A和B两支队伍,整个系列的比赛次数不超过2n-1场,胜者是首先获得n场胜利

Question

算法设计,老师给的题,9-1 在一次世界系列赛中有A和B两支队伍,整个系列
算法设计,老师给的题,
9-1 在一次世界系列赛中有A和B两支队伍,整个系列的比赛次数不超过2n-1场,胜者是首先获得n场胜利的队伍.假定比赛中没有平局,每场比赛的结果相互独立,而且对于任意一场比赛A队获胜的概率是常数p,则B队获胜的概率是q=1-p,设计一个动态规划的算法,计算A队最终获胜的概率

Answer 1

用f[i][j]表示 进行了i场,A队赢了j场的概率
转移：
f[i+1][j+1]+=f[i][j]*p 第i+1场A队获胜
f[i+1][j]+=f[i][j]*(1-p) 第i+1场B队获胜
初值：f[0][0]=1
在转移时,若i-j>=n (B队已经获胜) 或者 i>n (A队已经获胜) 那么就停止转移,将A队已经获胜的概率加入答案中