题意:
袋中有w白鼠,b黑鼠.
A - princess B - dragon
A,B轮流随机拿出一只, A先拿, B拿了一只之后会有一只鼠随机跑出.
先拿到一只白鼠的获胜.
问A获胜的概率.
思路:
概率DP.
要义是记忆化搜索. 因为概率是一回合一回合累加的, 询问后面的概率时, 会用到前面的概率.
dp记录的内容和问题有关, 这里只问A获胜的概率, 则dp[i][j]表示当袋中还有i只白鼠,j只黑鼠时, A获胜的概率.
首先考虑边界条件.
dp[i][0] = 1;
dp[0][j] = 0;
dp[i][j] =
(考虑所有可使A赢的情况)
@直接取到白鼠:
i / (i+j);
@A取到黑鼠. B取到黑鼠. 跑出一白鼠. ......
阅读全文