第一题是leetcode903原题

第二题动态规划:dp[i][j]表示i个红球和j个蓝球A的获胜概率.如果i=0,dp[i][j]=0.如果j=0,dp[i][j]=1.否则的话dp[i][j]由下列步骤求得:

dp[i][j]+=i/(i+j);//表示A直接取得红球的概率

如果j=1,那么dp[i][j]+=0.A取蓝球之后,B肯定获胜

如果j=2,dp[i][j]+=j/(i+j)*(j-1)/(i+j-1)*dp[i-1][j-2];j/(i+j)是A取蓝球的概率,在A取蓝球的基础上B再取蓝球A才有获胜机会,所以(j-1)/(i+j-1)表示B再取蓝球的概率,然后C只能从红球选一个,在ABC选一轮后,A的获胜概率就要加上dp[i-1][j-2],所以A获胜的概率为j/(i+j)*(j-1)/(i+j-1)*dp[i-1][j-2];

如果j>2,dp[i][j]+=j/(i+j)*(j-1)/(i+j-1)*(i/(i+j-2)*dp[i-1][j-2]+(j-2)/(i+j-2)*dp[i][j-3]);i/(i+j-2)*dp[i-1][j-2]+(j-2)/(i+j-2)*dp[i][j-3]表示A从蓝球选一个,B从蓝球选一个后,C分别从红球蓝球取出一个的A的获胜概率.

创作者周榜